{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d91c43cd",
   "metadata": {},
   "source": [
    "# Python机器学习（第15期）第4课书面作业\n",
    "学号：113727\n",
    "\n",
    "1. 周志华《机器学习》第93页4.3题，要求用python语言完成  \n",
    "试编程实现基于信息熵进行划分选择的决策树算法？并为表4.3 中数据生成一棵决策树。  \n",
    "2. 周志华《机器学习》第93页4.9题  \n",
    "试将4.4.2 节对缺失值的处理机制推广到基尼指数的计算中去。\n",
    "\n",
    "## 作业1\n",
    "试编程实现基于信息熵进行划分选择的决策树算法？并为表4.3 中数据生成一棵决策树。 "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6d641965",
   "metadata": {},
   "source": [
    "表4.3数据如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "id": "e5ea6b79",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>编号</th>\n",
       "      <th>色泽</th>\n",
       "      <th>根蒂</th>\n",
       "      <th>敲声</th>\n",
       "      <th>纹理</th>\n",
       "      <th>脐部</th>\n",
       "      <th>触感</th>\n",
       "      <th>密度</th>\n",
       "      <th>含糖率</th>\n",
       "      <th>好瓜</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>青绿</td>\n",
       "      <td>蜷缩</td>\n",
       "      <td>浊响</td>\n",
       "      <td>清晰</td>\n",
       "      <td>凹陷</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>0.697</td>\n",
       "      <td>0.460</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2</td>\n",
       "      <td>乌黑</td>\n",
       "      <td>蜷缩</td>\n",
       "      <td>沉闷</td>\n",
       "      <td>清晰</td>\n",
       "      <td>凹陷</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>0.774</td>\n",
       "      <td>0.376</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>3</td>\n",
       "      <td>乌黑</td>\n",
       "      <td>蜷缩</td>\n",
       "      <td>浊响</td>\n",
       "      <td>清晰</td>\n",
       "      <td>凹陷</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>0.634</td>\n",
       "      <td>0.264</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4</td>\n",
       "      <td>青绿</td>\n",
       "      <td>蜷缩</td>\n",
       "      <td>沉闷</td>\n",
       "      <td>清晰</td>\n",
       "      <td>凹陷</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>0.608</td>\n",
       "      <td>0.318</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5</td>\n",
       "      <td>浅白</td>\n",
       "      <td>蜷缩</td>\n",
       "      <td>浊响</td>\n",
       "      <td>清晰</td>\n",
       "      <td>凹陷</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>0.556</td>\n",
       "      <td>0.215</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>6</td>\n",
       "      <td>青绿</td>\n",
       "      <td>稍蜷</td>\n",
       "      <td>浊响</td>\n",
       "      <td>清晰</td>\n",
       "      <td>稍凹</td>\n",
       "      <td>软粘</td>\n",
       "      <td>0.403</td>\n",
       "      <td>0.237</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>7</td>\n",
       "      <td>乌黑</td>\n",
       "      <td>稍蜷</td>\n",
       "      <td>浊响</td>\n",
       "      <td>稍糊</td>\n",
       "      <td>稍凹</td>\n",
       "      <td>软粘</td>\n",
       "      <td>0.481</td>\n",
       "      <td>0.149</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>8</td>\n",
       "      <td>乌黑</td>\n",
       "      <td>稍蜷</td>\n",
       "      <td>浊响</td>\n",
       "      <td>清晰</td>\n",
       "      <td>稍凹</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>0.437</td>\n",
       "      <td>0.211</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>9</td>\n",
       "      <td>乌黑</td>\n",
       "      <td>稍蜷</td>\n",
       "      <td>沉闷</td>\n",
       "      <td>稍糊</td>\n",
       "      <td>稍凹</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>0.666</td>\n",
       "      <td>0.091</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>10</td>\n",
       "      <td>青绿</td>\n",
       "      <td>硬挺</td>\n",
       "      <td>清脆</td>\n",
       "      <td>清晰</td>\n",
       "      <td>平坦</td>\n",
       "      <td>软粘</td>\n",
       "      <td>0.243</td>\n",
       "      <td>0.267</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>11</td>\n",
       "      <td>浅白</td>\n",
       "      <td>硬挺</td>\n",
       "      <td>清脆</td>\n",
       "      <td>模糊</td>\n",
       "      <td>平坦</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>0.245</td>\n",
       "      <td>0.057</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>12</td>\n",
       "      <td>浅白</td>\n",
       "      <td>蜷缩</td>\n",
       "      <td>浊响</td>\n",
       "      <td>模糊</td>\n",
       "      <td>平坦</td>\n",
       "      <td>软粘</td>\n",
       "      <td>0.343</td>\n",
       "      <td>0.099</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>13</td>\n",
       "      <td>青绿</td>\n",
       "      <td>稍蜷</td>\n",
       "      <td>浊响</td>\n",
       "      <td>稍糊</td>\n",
       "      <td>凹陷</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>0.639</td>\n",
       "      <td>0.161</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>14</td>\n",
       "      <td>浅白</td>\n",
       "      <td>稍蜷</td>\n",
       "      <td>沉闷</td>\n",
       "      <td>稍糊</td>\n",
       "      <td>凹陷</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>0.657</td>\n",
       "      <td>0.198</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>14</th>\n",
       "      <td>15</td>\n",
       "      <td>乌黑</td>\n",
       "      <td>稍蜷</td>\n",
       "      <td>浊响</td>\n",
       "      <td>清晰</td>\n",
       "      <td>稍凹</td>\n",
       "      <td>软粘</td>\n",
       "      <td>0.360</td>\n",
       "      <td>0.370</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>15</th>\n",
       "      <td>16</td>\n",
       "      <td>浅白</td>\n",
       "      <td>蜷缩</td>\n",
       "      <td>浊响</td>\n",
       "      <td>模糊</td>\n",
       "      <td>平坦</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>0.593</td>\n",
       "      <td>0.042</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>16</th>\n",
       "      <td>17</td>\n",
       "      <td>青绿</td>\n",
       "      <td>蜷缩</td>\n",
       "      <td>沉闷</td>\n",
       "      <td>稍糊</td>\n",
       "      <td>稍凹</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>0.719</td>\n",
       "      <td>0.103</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    编号  色泽  根蒂  敲声  纹理  脐部  触感     密度    含糖率 好瓜\n",
       "0    1  青绿  蜷缩  浊响  清晰  凹陷  硬滑  0.697  0.460  是\n",
       "1    2  乌黑  蜷缩  沉闷  清晰  凹陷  硬滑  0.774  0.376  是\n",
       "2    3  乌黑  蜷缩  浊响  清晰  凹陷  硬滑  0.634  0.264  是\n",
       "3    4  青绿  蜷缩  沉闷  清晰  凹陷  硬滑  0.608  0.318  是\n",
       "4    5  浅白  蜷缩  浊响  清晰  凹陷  硬滑  0.556  0.215  是\n",
       "5    6  青绿  稍蜷  浊响  清晰  稍凹  软粘  0.403  0.237  是\n",
       "6    7  乌黑  稍蜷  浊响  稍糊  稍凹  软粘  0.481  0.149  是\n",
       "7    8  乌黑  稍蜷  浊响  清晰  稍凹  硬滑  0.437  0.211  是\n",
       "8    9  乌黑  稍蜷  沉闷  稍糊  稍凹  硬滑  0.666  0.091  否\n",
       "9   10  青绿  硬挺  清脆  清晰  平坦  软粘  0.243  0.267  否\n",
       "10  11  浅白  硬挺  清脆  模糊  平坦  硬滑  0.245  0.057  否\n",
       "11  12  浅白  蜷缩  浊响  模糊  平坦  软粘  0.343  0.099  否\n",
       "12  13  青绿  稍蜷  浊响  稍糊  凹陷  硬滑  0.639  0.161  否\n",
       "13  14  浅白  稍蜷  沉闷  稍糊  凹陷  硬滑  0.657  0.198  否\n",
       "14  15  乌黑  稍蜷  浊响  清晰  稍凹  软粘  0.360  0.370  否\n",
       "15  16  浅白  蜷缩  浊响  模糊  平坦  硬滑  0.593  0.042  否\n",
       "16  17  青绿  蜷缩  沉闷  稍糊  稍凹  硬滑  0.719  0.103  否"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import pandas as pd\n",
    "ds=pd.read_csv('watermelon_3a.csv')\n",
    "ds"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3be994dc",
   "metadata": {},
   "source": [
    "本题目的关键如下：\n",
    "1. 构建一颗基于C4.5的决策树；\n",
    "2. 能够处理上表中的连续型数据（密度、含糖量）。\n",
    "\n",
    "下面为编程实现部分："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "id": "d1f4a657",
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import log\n",
    "import operator\n",
    "import os\n",
    "\n",
    "import re\n",
    "from numpy import inf\n",
    "import copy\n",
    "\n",
    "# 计算信息熵\n",
    "def calcShannonEnt(dataSet, labelIndex):\n",
    "    # type: (list) -> float\n",
    "    numEntries = 0  # 样本数(按权重计算）\n",
    "    labelCounts = {}\n",
    "    for featVec in dataSet:  # 遍历每个样本\n",
    "        if featVec[labelIndex] != 'N':\n",
    "            weight = float(featVec[-2])\n",
    "            numEntries += weight\n",
    "            currentLabel = featVec[-1]  # 当前样本的类别\n",
    "            if currentLabel not in labelCounts.keys():  # 生成类别字典\n",
    "                labelCounts[currentLabel] = 0\n",
    "            labelCounts[currentLabel] += weight  # 数据集的倒数第二个值用来标记样本权重\n",
    "    shannonEnt = 0.0\n",
    "    for key in labelCounts:  # 计算信息熵\n",
    "        prob = float(labelCounts[key]) / numEntries\n",
    "        shannonEnt = shannonEnt - prob * log(prob, 2)\n",
    "    return shannonEnt\n",
    "\n",
    "def splitDataSet(dataSet, axis, value, LorR='N'):\n",
    "    \"\"\"\n",
    "    type: (list, int, string or float, string) -> list\n",
    "    划分数据集\n",
    "    axis:按第几个特征划分\n",
    "    value:划分特征的值\n",
    "    LorR: N 离散属性; L 小于等于value值; R 大于value值\n",
    "    \"\"\"\n",
    "    retDataSet = []\n",
    "    featVec = []\n",
    "    if LorR == 'N':  # 离散属性\n",
    "        for featVec in dataSet:\n",
    "            if featVec[axis] == value:\n",
    "                reducedFeatVec = featVec[:axis]\n",
    "                reducedFeatVec.extend(featVec[axis + 1:])\n",
    "                retDataSet.append(reducedFeatVec)\n",
    "    elif LorR == 'L':\n",
    "        for featVec in dataSet:\n",
    "            if featVec[axis] != 'N':\n",
    "                if float(featVec[axis]) < value:\n",
    "                    retDataSet.append(featVec)\n",
    "    elif LorR == 'R':\n",
    "        for featVec in dataSet:\n",
    "            if featVec[axis] != 'N':\n",
    "                if float(featVec[axis]) > value:\n",
    "                    retDataSet.append(featVec)\n",
    "    return retDataSet\n",
    "\n",
    "def splitDataSetWithNull(dataSet, axis, value, LorR='N'):\n",
    "    \"\"\"\n",
    "    type: (list, int, string or float, string) -> list\n",
    "    划分数据集\n",
    "    axis:按第几个特征划分\n",
    "    value:划分特征的值\n",
    "    LorR: N 离散属性; L 小于等于value值; R 大于value值\n",
    "    \"\"\"\n",
    "    retDataSet = []\n",
    "    nullDataSet = []\n",
    "    featVec = []\n",
    "    totalWeightV = calcTotalWeight(dataSet, axis, False)  # 非空样本权重\n",
    "    totalWeightSub = 0.0\n",
    "    if LorR == 'N':  # 离散属性\n",
    "        for featVec in dataSet:\n",
    "            if featVec[axis] == value:\n",
    "                reducedFeatVec = featVec[:axis]\n",
    "                reducedFeatVec.extend(featVec[axis + 1:])\n",
    "                retDataSet.append(reducedFeatVec)\n",
    "            elif featVec[axis] == 'N':\n",
    "                reducedNullVec = featVec[:axis]\n",
    "                reducedNullVec.extend(featVec[axis + 1:])\n",
    "                nullDataSet.append(reducedNullVec)\n",
    "    elif LorR == 'L':\n",
    "        for featVec in dataSet:\n",
    "            if featVec[axis] != 'N':\n",
    "                if float(featVec[axis]) < value:\n",
    "                    retDataSet.append(featVec)\n",
    "            elif featVec[axis] == 'N':\n",
    "                nullDataSet.append(featVec)\n",
    "    elif LorR == 'R':\n",
    "        for featVec in dataSet:\n",
    "            if featVec[axis] != 'N':\n",
    "                if float(featVec[axis]) > value:\n",
    "                    retDataSet.append(featVec)\n",
    "            elif featVec[axis] == 'N':\n",
    "                nullDataSet.append(featVec)\n",
    "\n",
    "    totalWeightSub = calcTotalWeight(retDataSet, -1, True)  # 计算此分支中非空样本的总权重\n",
    "    for nullVec in nullDataSet:  # 把缺失值样本按权值比例划分到分支中\n",
    "        nullVec[-2] = float(nullVec[-2]) * totalWeightSub / totalWeightV\n",
    "        retDataSet.append(nullVec)\n",
    "\n",
    "    return retDataSet\n",
    "\n",
    "def calcTotalWeight(dataSet, labelIndex, isContainNull):\n",
    "    \"\"\"\n",
    "    type: (list, int, bool) -> float\n",
    "    计算样本集对某个特征值的总样本树（按权重计算）\n",
    "    :param dataSet: 数据集\n",
    "    :param labelIndex: 特征值索引\n",
    "    :param isContainNull: 是否包含空值的样本\n",
    "    :return: 返回样本集的总权重值\n",
    "    \"\"\"\n",
    "    totalWeight = 0.0\n",
    "    for featVec in dataSet:  # 遍历每个样本\n",
    "        weight = float(featVec[-2])\n",
    "        if isContainNull is False and featVec[labelIndex] != 'N':\n",
    "            totalWeight += weight  # 非空样本树，按权重计算\n",
    "        if isContainNull is True:\n",
    "            totalWeight += weight  # 总样本数，按权重计算\n",
    "    return totalWeight\n",
    "\n",
    "def calcGain(dataSet, labelIndex, labelPropertyi):\n",
    "    \"\"\"\n",
    "    type: (list, int, int) -> float, int\n",
    "    计算信息增益,返回信息增益值和连续属性的划分点\n",
    "    dataSet: 数据集\n",
    "    labelIndex: 特征值索引\n",
    "    labelPropertyi: 特征值类型，0为离散，1为连续\n",
    "    \"\"\"\n",
    "    baseEntropy = calcShannonEnt(dataSet, labelIndex)  # 计算根节点的信息熵\n",
    "    featList = [example[labelIndex] for example in dataSet]  # 特征值列表\n",
    "    uniqueVals = set(featList)  # 该特征包含的所有值\n",
    "    newEntropy = 0.0\n",
    "    totalWeight = 0.0\n",
    "    totalWeightV = 0.0\n",
    "    totalWeight = calcTotalWeight(dataSet, labelIndex, True)  # 总样本权重\n",
    "    totalWeightV = calcTotalWeight(dataSet, labelIndex, False)  # 非空样本权重\n",
    "    if labelPropertyi == 0:  # 对离散的特征\n",
    "        for value in uniqueVals:  # 对每个特征值，划分数据集, 计算各子集的信息熵\n",
    "            if value != 'N':\n",
    "                subDataSet = splitDataSet(dataSet, labelIndex, value)\n",
    "                totalWeightSub = 0.0\n",
    "                totalWeightSub = calcTotalWeight(subDataSet, labelIndex, True)\n",
    "                prob = totalWeightSub / totalWeightV\n",
    "                newEntropy += prob * calcShannonEnt(subDataSet, labelIndex)\n",
    "    else:  # 对连续的特征\n",
    "        uniqueValsList = list(uniqueVals)\n",
    "        if 'N' in uniqueValsList:\n",
    "            uniqueValsList.remove('N')\n",
    "        sortedUniqueVals = sorted(uniqueValsList)  # 对特征值排序\n",
    "        listPartition = []\n",
    "        minEntropy = inf\n",
    "        if len(sortedUniqueVals) == 1:  # 如果只有一个值，可以看作只有左子集，没有右子集\n",
    "            totalWeightLeft = calcTotalWeight(dataSet, labelIndex, True)\n",
    "            probLeft = totalWeightLeft / totalWeightV\n",
    "            minEntropy = probLeft * calcShannonEnt(dataSet, labelIndex)\n",
    "        else:\n",
    "            for j in range(len(sortedUniqueVals) - 1):  # 计算划分点\n",
    "                partValue = (float(sortedUniqueVals[j]) + float(\n",
    "                    sortedUniqueVals[j + 1])) / 2\n",
    "                # 对每个划分点，计算信息熵\n",
    "                dataSetLeft = splitDataSet(dataSet, labelIndex, partValue, 'L')\n",
    "                dataSetRight = splitDataSet(dataSet, labelIndex, partValue, 'R')\n",
    "                totalWeightLeft = 0.0\n",
    "                totalWeightLeft = calcTotalWeight(dataSetLeft, labelIndex, True)\n",
    "                totalWeightRight = 0.0\n",
    "                totalWeightRight = calcTotalWeight(dataSetRight, labelIndex, True)\n",
    "                probLeft = totalWeightLeft / totalWeightV\n",
    "                probRight = totalWeightRight / totalWeightV\n",
    "                Entropy = probLeft * calcShannonEnt(dataSetLeft, labelIndex) + \\\n",
    "                          probRight * calcShannonEnt(dataSetRight, labelIndex)\n",
    "                if Entropy < minEntropy:  # 取最小的信息熵\n",
    "                    minEntropy = Entropy\n",
    "        newEntropy = minEntropy\n",
    "    gain = totalWeightV / totalWeight * (baseEntropy - newEntropy)\n",
    "    return gain\n",
    "\n",
    "def calcGainRatio(dataSet, labelIndex, labelPropertyi):\n",
    "    \"\"\"\n",
    "    type: (list, int, int) -> float, int\n",
    "    计算信息增益率,返回信息增益率和连续属性的划分点\n",
    "    dataSet: 数据集\n",
    "    labelIndex: 特征值索引\n",
    "    labelPropertyi: 特征值类型，0为离散，1为连续\n",
    "    \"\"\"\n",
    "    baseEntropy = calcShannonEnt(dataSet, labelIndex)  # 计算根节点的信息熵\n",
    "    featList = [example[labelIndex] for example in dataSet]  # 特征值列表\n",
    "    uniqueVals = set(featList)  # 该特征包含的所有值\n",
    "    newEntropy = 0.0\n",
    "    bestPartValuei = None\n",
    "    IV = 0.0\n",
    "    totalWeight = 0.0\n",
    "    totalWeightV = 0.0\n",
    "    totalWeight = calcTotalWeight(dataSet, labelIndex, True)  # 总样本权重\n",
    "    totalWeightV = calcTotalWeight(dataSet, labelIndex, False)  # 非空样本权重\n",
    "    if labelPropertyi == 0:  # 对离散的特征\n",
    "        for value in uniqueVals:  # 对每个特征值，划分数据集, 计算各子集的信息熵\n",
    "            subDataSet = splitDataSet(dataSet, labelIndex, value)\n",
    "            totalWeightSub = 0.0\n",
    "            totalWeightSub = calcTotalWeight(subDataSet, labelIndex, True)\n",
    "            if value != 'N':\n",
    "                prob = totalWeightSub / totalWeightV\n",
    "                newEntropy += prob * calcShannonEnt(subDataSet, labelIndex)\n",
    "            prob1 = totalWeightSub / totalWeight\n",
    "            IV -= prob1 * log(prob1, 2)\n",
    "    else:  # 对连续的特征\n",
    "        uniqueValsList = list(uniqueVals)\n",
    "        if 'N' in uniqueValsList:\n",
    "            uniqueValsList.remove('N')\n",
    "            # 计算空值样本的总权重，用于计算IV\n",
    "            totalWeightN = 0.0\n",
    "            dataSetNull = splitDataSet(dataSet, labelIndex, 'N')\n",
    "            totalWeightN = calcTotalWeight(dataSetNull, labelIndex, True)\n",
    "            probNull = totalWeightN / totalWeight\n",
    "            if probNull > 0.0:\n",
    "                IV += -1 * probNull * log(probNull, 2)\n",
    "\n",
    "        sortedUniqueVals = sorted(uniqueValsList)  # 对特征值排序\n",
    "        listPartition = []\n",
    "        minEntropy = inf\n",
    "\n",
    "        if len(sortedUniqueVals) == 1:  # 如果只有一个值，可以看作只有左子集，没有右子集\n",
    "            totalWeightLeft = calcTotalWeight(dataSet, labelIndex, True)\n",
    "            probLeft = totalWeightLeft / totalWeightV\n",
    "            minEntropy = probLeft * calcShannonEnt(dataSet, labelIndex)\n",
    "            IV = -1 * probLeft * log(probLeft, 2)\n",
    "        else:\n",
    "            for j in range(len(sortedUniqueVals) - 1):  # 计算划分点\n",
    "                partValue = (float(sortedUniqueVals[j]) + float(\n",
    "                    sortedUniqueVals[j + 1])) / 2\n",
    "                # 对每个划分点，计算信息熵\n",
    "                dataSetLeft = splitDataSet(dataSet, labelIndex, partValue, 'L')\n",
    "                dataSetRight = splitDataSet(dataSet, labelIndex, partValue, 'R')\n",
    "                totalWeightLeft = 0.0\n",
    "                totalWeightLeft = calcTotalWeight(dataSetLeft, labelIndex, True)\n",
    "                totalWeightRight = 0.0\n",
    "                totalWeightRight = calcTotalWeight(dataSetRight, labelIndex, True)\n",
    "                probLeft = totalWeightLeft / totalWeightV\n",
    "                probRight = totalWeightRight / totalWeightV\n",
    "                Entropy = probLeft * calcShannonEnt(\n",
    "                    dataSetLeft, labelIndex) + probRight * calcShannonEnt(dataSetRight, labelIndex)\n",
    "                if Entropy < minEntropy:  # 取最小的信息熵\n",
    "                    minEntropy = Entropy\n",
    "                    bestPartValuei = partValue\n",
    "                    probLeft1 = totalWeightLeft / totalWeight\n",
    "                    probRight1 = totalWeightRight / totalWeight\n",
    "                    IV += -1 * (probLeft1 * log(probLeft1, 2) + probRight1 * log(probRight1, 2))\n",
    "\n",
    "        newEntropy = minEntropy\n",
    "    gain = totalWeightV / totalWeight * (baseEntropy - newEntropy)\n",
    "    if IV == 0.0:  # 如果属性只有一个值，IV为0，为避免除数为0，给个很小的值\n",
    "        IV = 0.0000000001\n",
    "    gainRatio = gain / IV\n",
    "    return gainRatio, bestPartValuei\n",
    "\n",
    "# 选择最好的数据集划分方式\n",
    "def chooseBestFeatureToSplit(dataSet, labelProperty):\n",
    "    \"\"\"\n",
    "    type: (list, int) -> int, float\n",
    "    :param dataSet: 样本集\n",
    "    :param labelProperty: 特征值类型，1 连续， 0 离散\n",
    "    :return: 最佳划分属性的索引和连续属性的划分值\n",
    "    \"\"\"\n",
    "    numFeatures = len(labelProperty)  # 特征数\n",
    "    bestInfoGainRatio = 0.0\n",
    "    bestFeature = -1\n",
    "    bestPartValue = None  # 连续的特征值，最佳划分值\n",
    "    gainSum = 0.0\n",
    "    gainAvg = 0.0\n",
    "    for i in range(numFeatures):  # 对每个特征循环\n",
    "        infoGain = calcGain(dataSet, i, labelProperty[i])\n",
    "        gainSum += infoGain\n",
    "    gainAvg = gainSum / numFeatures\n",
    "    for i in range(numFeatures):  # 对每个特征循环\n",
    "        infoGainRatio, bestPartValuei = calcGainRatio(dataSet, i, labelProperty[i])\n",
    "        infoGain = calcGain(dataSet, i, labelProperty[i])\n",
    "        if infoGainRatio > bestInfoGainRatio and infoGain > gainAvg:  # 取信息增益高于平均增益且信息增益率最大的特征\n",
    "            bestInfoGainRatio = infoGainRatio\n",
    "            bestFeature = i\n",
    "            bestPartValue = bestPartValuei\n",
    "    return bestFeature, bestPartValue\n",
    "\n",
    "# 通过排序返回出现次数最多的类别\n",
    "def majorityCnt(classList, weightList):\n",
    "    classCount = {}\n",
    "    for i in range(len(classList)):\n",
    "        if classList[i] not in classCount.keys():\n",
    "            classCount[classList[i]] = 0.0\n",
    "        classCount[classList[i]] += round(float(weightList[i]),1)\n",
    "\n",
    "    # python 2.7\n",
    "    # sortedClassCount = sorted(classCount.iteritems(),\n",
    "    #                         key=operator.itemgetter(1), reverse=True)\n",
    "    sortedClassCount = sorted(classCount.items(),\n",
    "                              key=operator.itemgetter(1), reverse=True)\n",
    "    if len(sortedClassCount) == 1:\n",
    "        return (sortedClassCount[0][0],sortedClassCount[0][1],0.0)\n",
    "    return (sortedClassCount[0][0], sortedClassCount[0][1], sortedClassCount[1][1])\n",
    "\n",
    "# 创建树, 样本集 特征 特征属性（0 离散， 1 连续）\n",
    "def createTree(dataSet, labels, labelProperty):\n",
    "    classList = [example[-1] for example in dataSet]  # 类别向量\n",
    "    weightList = [example[-2] for example in dataSet]  # 权重向量\n",
    "    if classList.count(classList[0]) == len(classList):  # 如果只有一个类别，返回\n",
    "        totalWeiht = calcTotalWeight(dataSet,0,True) #计算总权重\n",
    "        return (classList[0], round(totalWeiht,1),0.0)#最后一个0表示啥?\n",
    "    #totalWeight = calcTotalWeight(dataSet, 0, True)\n",
    "    #下面这个判断有问题吧？最后一列是目标变量，倒数第2列是表示权重的辅助列，如果特征被遍历完了，这个判断应该是：\n",
    "    #if len(dataSet[0])==2:\n",
    "    if len(dataSet[0]) == 2:  # 如果所有特征都被遍历完了，返回出现次数最多的类别\n",
    "        return majorityCnt(classList,weightList)\n",
    "    \n",
    "    bestFeat, bestPartValue = chooseBestFeatureToSplit(dataSet,\n",
    "                                                       labelProperty)  # 最优分类特征的索引\n",
    "    if bestFeat == -1:  # 如果无法选出最优分类特征，返回出现次数最多的类别\n",
    "        return majorityCnt(classList, weightList)\n",
    "    if labelProperty[bestFeat] == 0:  # 对离散的特征\n",
    "        bestFeatLabel = labels[bestFeat]\n",
    "        myTree = {bestFeatLabel: {}}\n",
    "        labelsNew = copy.copy(labels)\n",
    "        labelPropertyNew = copy.copy(labelProperty)\n",
    "        del (labelsNew[bestFeat])  # 已经选择的特征不再参与分类\n",
    "        del (labelPropertyNew[bestFeat])\n",
    "        featValues = [example[bestFeat] for example in dataSet]\n",
    "        uniqueValue = set(featValues)  # 该特征包含的所有值\n",
    "        uniqueValue.discard('N')\n",
    "        for value in uniqueValue:  # 对每个特征值，递归构建树\n",
    "            subLabels = labelsNew[:]\n",
    "            subLabelProperty = labelPropertyNew[:]\n",
    "            myTree[bestFeatLabel][value] = createTree(\n",
    "                splitDataSetWithNull(dataSet, bestFeat, value), subLabels,\n",
    "                subLabelProperty)\n",
    "    else:  # 对连续的特征，不删除该特征，分别构建左子树和右子树\n",
    "        bestFeatLabel = labels[bestFeat] + '<' + str(bestPartValue)\n",
    "        myTree = {bestFeatLabel: {}}\n",
    "        subLabels = labels[:]\n",
    "        subLabelProperty = labelProperty[:]\n",
    "        # 构建左子树\n",
    "        valueLeft = 'Y'\n",
    "        myTree[bestFeatLabel][valueLeft] = createTree(\n",
    "            splitDataSetWithNull(dataSet, bestFeat, bestPartValue, 'L'), subLabels,\n",
    "            subLabelProperty)\n",
    "        # 构建右子树\n",
    "        valueRight = 'N'\n",
    "        myTree[bestFeatLabel][valueRight] = createTree(\n",
    "            splitDataSetWithNull(dataSet, bestFeat, bestPartValue, 'R'), subLabels,\n",
    "            subLabelProperty)\n",
    "    return myTree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "id": "f7613f8f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAV0AAADoCAYAAABM+DfFAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8QVMy6AAAACXBIWXMAAAsTAAALEwEAmpwYAABETElEQVR4nO3deVxU5f7A8Q8gixu7CMgiLogKKlJairjkVUxJEUHF3EvbtbLsV1ZezW6WWbl0M3PJStxwxe26oYBbigvigiiyiCLLACGyzvn94WWuKJrAzBxmeN6v17ysmTPnfM/DOd855znPYiBJkoQgCIKgFYZyByAIglCfiKQryMrV1RUDAwOtv1xdXeXedaGeMhDVC4KcDAwMSE9P1/p2HR0dEYe+IAdxpSsIgqBFIukKgiBokUi6giAIWiSSriAIghaJpCvUSTdv3uStt95S/X9eXh4zZsxQ/f+hQ4dYs2YNa9as4cCBA/j6+hISEkL79u0JCQmhY8eOlJaWyhG6IDyRSLpCnbR161b69u0LQFFREebm5ri6ulJeXk5JSQkNGzYkKSmJS5cu0aRJExwdHdmwYQMdOnRgw4YNdOzYEWNjY5n3QhAe1UDuAAThYQqFgiNHjvDTTz8xffp0jh49iqWlJba2tixfvpxWrVqxYMECfHx8uHv3Lt27dyczM5OgoCDi4+MJCgri4sWLcu+GIFRJJF2hzlmyZAlFRUWMGzeOiRMn0r17d5RKJWPGjOGll15i3bp1xMXFERkZSUlJCe3bt6dZs2Zs2LCBoKAgwsPDCQkJQZIkDAwM5N4dQahEVC8Idc4HH3zAvHnzcHd3Z/jw4Xh4eJCQkEB5eTmSJGFmZkaLFi1o1aoVrq6uNG/enPT0dEJCQrh48SIhISHEx8eLOl2hThJJV6hz0tLSGDduHEVFRXzyySd4eXlx7Ngx9u3bx/PPPw/c71Hm4uKCk5MTzZs3Jzo6ulKdbnx8PCYmJjLviSA8SlQvCHVO8+bN+f777+nSpQtNmjTB0NCQYcOG8f7777N3795Ky16/fp21a9eybds2JElSXemWlJSwePFinJ2dZdoLQaiaSLpCnfPnn3/y66+/IkkStra2vPnmm+zZs4d27dqxcuVKZsyYwZEjR/j555/x9vama9euhIaGAhAUFMSGDRtk3gNBeDwx4I0gq6oGvMnMzKSoqAhnZ2fmzZvHkSNHmDt3Lt26dWPlypWsXLmSt956iyFDhtCkSRM2bNjApk2bAIiLi8PLywuAQYMGMXHixCq3Kwa8EeQikq4gq4qkGxcXR9u2bTEzM6v0+Z07d7CxscHIyEj1XklJCcbGxqqWCeXl5RgaGlZqqSBJEkqlEiMjIyRJIjY2lq5du6qWEUlXkIt4kCbILiwsjLFjx5Kbm/vIZ3Z2dpUSLoCJiUmlBGtkZPRI0zADAwPV95RKJTNnzuSf//wnSqVS/TsgCNUgrnQF2UiShKGhIc7Ozqxdu5bWrVtrbFu5ubmMHz8eFxcXFi5ciKurq7jSFWQhrnQFWSiVSt577z0Atm3bptGEC2BpaUlYWBh5eXmPrecVBG0QSVfQupKSEsaNG8epU6cAsLe318p2GzVqxIoVK7C1tQUgOztbK9sVhAeJ6gVBq+7evUtQUBAmJiasX78eDw8PUlJStB5H06ZNcXJyYu/evaItr6BV4kpX0Jrs7GxeeOEFHB0d2bx5Mw0bNiQ5ORlJkqr9atu2LVlZWTX6riRJ5OfnM2nSJHx9fbl06ZLcRSPUIyLpClqRmppKr1696NOnDytWrKBBg9r1yykoKKC4uLhW65gxYwZz586lb9++nDhxolbrEoSnJZKuoHEXL17E19eXV199la+++qpOjfw1btw4VqxYwZAhQ9izZ4/c4Qj1gEi6gkYdO3aMfv36MW/ePN599125w6nS4MGD2bZtG+PHj2ft2rVyhyPoOTH2gqAxu3fvZty4caxZs4ZBgwbJHc4T9ejRgwMHDjBo0CAyMzOZNm2a3CEJekokXUEjfv/9d2bMmMH27dtVwzHWdZ6enkRHRzNgwAAyMjKYN29enaoKEfSDqF4Q1G7hwoV8/PHHHDx4UGcSbgVXV1eio6PZv38/r776KmVlZXKHJOgZkXQFtZEkiY8++ojly5cTExNDhw4d5A6pRpo1a8bBgwdJSUkhODiYe/fuyR2SoEdE0hXUoqysjFdeeYXIyEiio6N1vsNBkyZNiIiIwMzMDH9//yoH4xGEmhBJV6i1e/fuERQURHp6OgcOHMDGxkbukNTCxMSEP/74g06dOtG7d29u3bold0iCHhBJV6gVhULBgAEDaNq0Kdu3b6dx48Zyh6RWhoaGLFq0iODgYHx9fUlMTJQ7JEHHiaQr1Fh6ejp+fn4888wzrFmzBmNjY7lD0ggDAwNmzZrFzJkz8fPzIzY2Vu6QBB0mkq5QIwkJCfTs2ZMxY8awcOFCDA31/1CaMmUKS5Yswd/fn4MHD8odjqCj9P9MEdTu1KlT9O7dm1mzZvHRRx/Vq7asw4cPZ/369YwaNYrw8HC5wxF0kOgcIVTL/v37CQ0NZfny5QwdOlTucGTRt29f9u7dy+DBg8nKymLq1KlyhyToEJF0hae2YcMG3n77bcLDw+nVq5fc4cjK29ubqKgoVe+1Tz/9tF5d8Qs1J6oXhKeydOlS3nvvPfbt21fvE26F1q1bExMTw+bNm3n77bfFpJfCUxFJV3giSZL4/PPP+eGHH4iKiqJTp05yh1Sn2Nvbc/jwYS5cuEBoaGitx/gV9J9IusJjlZeX8/rrrxMREUF0dDRubm5yh1QnWVhYsGfPHoqLixkyZAh//fWX3CEJdZhIukKVioqKGDlyJFevXuXQoUPY2dnJHVKNKZVKSkpKNLoNMzMzNm7cSMuWLenXrx+ZmZlq34Y29kPQPDExZT21YsUKQkNDuXPnDsXFxRw+fJizZ8/y7rvvkpeXx4wZM2jWrBm//fYbpqamTJo0iUWLFtGwYUOuX7/O7t276devH56enrLE7+joyKlTpygsLOSzzz7j999/B+Cll14iIiKCwYMHs2PHDtVYEKWlpeTl5TFw4EBSUlLo1KkT48aNw9jYmE8//ZQxY8aoJS5Jkvj000/ZuHEje/fupWXLln/7nbKyMi5dusSBAwdITU1lxIgRtGvXjg8//JB33nmHzMxMTp06RXFxsdb2Q9AccaVbT9nb2zNlyhTOnDnD/v37uXjxIqmpqWzbto3AwEAKCwtJTEzE2dmZoqIiiouLMTIyYu7cucyYMYN79+5RVFQk925gZmaGiYkJCQkJ9O3bl5MnT9KnTx+OHz9O3759MTU1JT4+nvz8fIqKijA2NqZBgwYYGBjw+uuv89FHH2FiYqK2eAwMDPjiiy9488036dWrF3FxcX/7nYSEBFasWMHvv//O559/zp07d1i4cCFmZmbk5eXx+eef4+fnp9X9EDRHNBmrh/Lz8+nXrx+DBw9m+/btREREkJ2dzZ07dzhw4AAdOnRg+PDhvPDCCyxYsIDo6GguXLjAsmXLaNy4MePHj6dHjx6yn+SJiYlERkaSkJDAlStXGD16NFlZWTg5OXHlyhXMzc3x9PRk4MCBHD9+nFatWvH++++r6l4bN26MkZERTZo0UXts77zzDra2tvTv35/NmzfTs2fPxy7r4uLCxx9/THBwMIWFhQwZMgR3d3eWLl2KpaUla9euxcLCQpb9ENRPXOnWQzdu3CAwMJADBw5w5MgRvL29cXFxISMjAz8/P3r37k1JSQlTp07l4MGD9O/fn9u3b/Paa69hbGxMTEwMAQEBnDx5Utb9aNOmDfb29jRt2pQOHTpw6NAh9u/fz+rVqzl27Bjr168nIiKCHTt2cObMGdq3b893333Hhx9+yOjRo7l27RqXL1/WWHyhoaGsWbOGYcOGERER8djl9uzZw8iRIzl//jzjx49n+fLlDBgwgOjoaMaOHUuXLl1YsmSJbPshqJe40q2HOnXqREREBJIkYWdnx9ixY7l48SJt27bl3r17tGzZkqKiIpYtW8aCBQs4ffo0CoWCiRMn4u3tTVBQEDdv3sTf31/W/VAqlaxdu5YGDRowc+ZMjIyMmD59uurz5cuXM2bMGDZu3Ii7uztFRUVMmzYNExMTxowZQ9euXbG1tdVojAMHDiQiIoKhQ4fy1VdfMWHChEeWGTFiBLm5uSgUCubPn8/Vq1fp168fffv2BeCXX34hKCiIP//8U7b9ENRHJN16qkGDBixevJh79+5x+fJl5syZQ5cuXTh//jypqak0a9ZMtezSpUvx8/NjxIgR7Nu3j4CAABkj/59Vq1bRq1cvUlNTmTdvHgUFBSgUCmbMmMGCBQuYO3cuhw8f5vbt23Tt2pXdu3czYcIE7O3tuX79OufOncPExIQRI0ZoNM7u3bsTGRnJwIEDyczM5IMPPqj0+Z07d/jtt99o2LAhH3zwAYGBgdjZ2dGmTRsAzM3NycjIkH0/BPUQSbee2rdvHwcOHCAmJoZnn30WJycnsrKyyMvLw8DAAEmSmDp1Kqmpqfz0009s3ryZwYMHs2rVqjrTXjcwMJAmTZowe/Zsbt++zRtvvAHAlStXVEnp9ddf57PPPuPkyZOMHDmSQYMGYWJigru7O2+++SYZGRlaidXDw4OYmBgGDhzInTt3mD9/vmpktuXLl/Puu++yePFidu/ezdatW1m4cCHHjh0D4OrVq5w7d65O7IdQe6JOtx4qLS3ltdde4+zZsyxbtozk5GR++eUXfvnlF3bu3AlASUkJy5YtIzg4mBdffBG4P36uoaEhZmZmlJaWyrkLAFhbW9Ogwf3rBh8fHw4dOoSXlxf79u3Dw8ODpUuXMnLkSNzc3JAkibKyMiZMmMCGDRuIj49XdWfW1rCUTk5OREVFERMTw8SJE1Vl+NFHHzFs2DBKS0tp0KABkiQxY8YMoqOjiY6OZuDAgQwYMKDO7IdQO+KvVM8olUrGjx9PUVERx44dw87OjtDQUCIjI4mMjMTPzw9PT0/69++Pi4sLS5cuVSXZjRs38sorrwBQUFAg857cV1paSmlpKeHh4YwePZo33niDZ599lmXLlvH222+zevVqiouLKS4uplWrVkyaNInDhw8zduxYbt26xbJly7Ta1tja2pr9+/eTlZWlappnZGQEgKmpKUClrsQLFizgxIkTNGvWrE7th1BzonNEPVJSUsKECRO4efMm27Ztw9LS8qm/W1RUhJmZmeaCq6aKzhGOjo7A/Q4GFVe9D6rq/fLycpRKJcbGxiiVSlmuEEtLS5k8eTKJiYlERERgbW1d5XKP2y+oG/shVJ/4K9UTBQUFBAQEUFhYyJ49e6qVcIE6lXCr8rjEVNX7RkZGqqmF5EpUxsbGrF69mh49euDn50daWlqVyz1uv6Bu7IdQfeIvVQ9kZWXxwgsv4OzszKZNm2jYsKHcIQncT5QLFixg/Pjx+Pr6ira29YRIunouOTkZX19f+vfvz/Lly5945STI44MPPuDzzz+nT58+snc4ETRPJF09Fh8fj6+vL6+//jrz5s0TMxvUYRMnTmT58uUMGTKE//znP3KHI2iQSLp66ujRo/Tr14/58+czbdo0ucMRnkJAQACbN29m7NixhIWFyR2OoCHiXlMP7dy5kwkTJvDbb7/J3lVXqB5fX1/279/PoEGDyMzM5J133pE7JEHNRNLVM7/++iszZ84kIiKC7t27yx2OUANeXl5ER0czYMAAMjMzmTNnjqga0iMi6eqRBQsWsHjxYiIjI/Hw8JA7HKEWWrZsSXR0NC+++CJ37tzhxx9/VHWiEHSbqNPVA5Ik8eGHH7Jq1SpiYmJEwtUTdnZ2HDp0iGvXrhEcHFwnBo0Xak8kXR1XWlrKxIkTiY6OJioqCicnJ7lDEtSoadOm7Ny5E2NjY/z9/cnLy5M7JKGWRNLVYYWFhQQGBpKZmcn+/fsf25VU0G2mpqasXbsWT09P+vTpw+3bt+UOSagFkXR1VE5ODv/4xz+wtrZm69atNGrUSO6QBA0yMjJi8eLFBAYG4uvry7Vr1+QOSaghkXR1UFpaGn5+fjz//POsXr1a1f9e0G8GBgZ89tlnzJgxg169enHmzBm5QxJqQCRdHXP58mV8fX0ZP348CxYsEAOd1EOvvfYaixYtYuDAgURGRsodjlBN4ozVIRXTi8+ePfuRKV+E+mXEiBGsW7eOkJAQNm/eLHc4QjWIdro64j//+Q9jxoxh5cqVdWaOMkFe/fr1Y8+ePQwZMoTs7GxeffVVuUMSnoJIujogLCyM6dOns3XrVnr27Cl3OEId0rVrV44cOcKAAQPIyMjgk08+Eb3X6jiRdOu4RYsW8c0333DgwAExHYtQpTZt2hATE4O/vz937tzh+++/F3X9dZj4y9RRkiQxa9Ysli5dSnR0tEi4whM5ODhw+PBhzp07x5gxYygpKZE7JOExRNKtg8rKypg6dSp79+4lOjoaV1dXuUMSdIClpSV79uzh3r17BAQE1JnJQ4XKRNKtY4qKiggODiYpKYmDBw/SrFkzuUMSdEjDhg3ZtGkTTk5O9OvXj6ysLLlDEh4ikm4dkpeXh7+/P6ampuzcuZOmTZvKHZKggxo0aMAvv/xC//798fX1JTk5We6QhAeIpFtH3Lp1i969e+Pl5cXatWsxMTGROyRBhxkYGPDll1/y+uuv4+vrS3x8vNwhCf8lkm4dkJiYiK+vLyNGjGDRokXiybOgNtOmTeOrr76iX79+HD16VO5wBETSlV1sbCx+fn7MnDmTWbNmiTaWgtqNGTOGX3/9laFDh7Jz5065w6n3RNKV0cGDB/H392fJkiVMmTJF7nAEPebv709ERASTJ09mzZo1codTr4nOETLZtGkTb7zxBhs2bKBPnz5yhyPUA927d+fQoUMMHDiQO3fuMGPGDLlDqpdE0pXBTz/9xJw5c9i7dy/e3t5yhyPUI+3btycmJkaVeOfPny+qtLRMVC9okSRJzJkzh2+++YaoqCiRcAVZODs7ExUVRVRUFJMmTaKsrEzukOoVkXS1pLy8nLfffpstW7YQExND69at5Q5JqMdsbGzYv38/GRkZBAYGUlhYKHdI9YZIuhr0888/U1xcTHFxMaGhocTHxxMZGYm9vb3coeksSZKe+P/C02vcuDHbtm3D0tKSAQMGoFAoAFi6dClKpVLm6PSXSLoakpSUxMcff8xff/3F4MGDKSsrY/fu3VhYWMgdmk574YUXOHfuHAB//fUX7dq1o7S0VOaodJexsTG//vor3bp1w8/Pj5s3b7JixQoOHjwod2h6SyRdDVm1ahXDhg3D39+f1q1bs2HDBszMzOQOS+cFBAQwZ84c4H4Zd+vWTcwRV0uGhoZ8++23vPzyy/j6+jJ48GBWrFghd1h6y0AS92dqV15ejrOzM8bGxgQEBNCuXTsA3n77bZkj032FhYW0bt1adXUbHR2Nh4eHzFHpvg0bNnDjxg2KiopYunQphYWFJCcnY21tLXdoekdc6WrAmjVruHXrFvfu3SM8PJzY2Fg6duwod1h6oVGjRnz44Yfk5OTQu3dvkXDVxN3dneTkZFavXk15eTl3795V3VEI6iWudDVg06ZNREREMH36dDp37izaQapZYWEhDg4OHDhwgGeeeUbucPSKJElcvXqVH3/8kRYtWogJUDVAZ5Kuq6srKSkpcochKxcXF70cpk+SJAoLC8nOzq70UigUNX6KbmFhgY2NTaWXubm5+AH8G3KdZ/p6bFdFZ5KugYEB6enpcochK0dHR51uIpWWlsbp06dVr5SUFLKzs8nJycHAwABra2usrKxULwsLC4yMjKq9HUmSyM/PJzc3F4VCQU5ODgqFgqKiIqysrLC1tcXBwQFvb298fHzo2rUr7u7uIiEj33mm68d2dYikq0N09cAsLy9n8uTJ7NixA29vbzw9PfH09MTV1VWVYBs1aqTxOIqLi1WJ+ObNm8THx3PhwgXOnDlDy5Yt2bFjB1ZWVhqPoy4TSVfzRNLVIbp6YK5Zs4YlS5YQFhamleRaXeXl5Xz00UdYW1uzaNEiucORlUi6midaLwgat3HjRsaNG1cnEy6AkZERU6ZMYfPmzfXmxBfkUy+TrpieWnuKi4uJjIykX79+cofyRG3atMHMzEzV202ovdzcXEpLS1Xdi4X79GpoxzVr1lBUVPTEAcETExOZNWsW69atA+5Pd96gQeViyMzM5MqVK/j6+j71thUKBefPn8fT0xMbG5ua7YAeunHjBnZ2dmqpK504cSJ3794F7j8sKysrU/VGKy4uZtu2bTVet4GBAR07duTixYt06dKl1rHqm4yMDD766CPmz5+Pubk5ZmZmREZGkp6eTmhoKAClpaWUl5ervvPzzz/j4eHBgQMHmDNnDo0bN37kXKuPdLoEysrKaNeuneokyc/Px9zcnL179wL3E+yqVav47bffSE1NVd3empiYMHbsWJRKJSYmJqxatUq1zjt37jBnzhzmzp0LwHvvvcfVq1d54YUXmD59epVx5ObmMm7cOPr3788///lPNm7ciJGREW+99RZZWVl06tSJr7/+Grif0F999VW2bt2q2ofnnnsOV1dXAL744gvat2+v7qKSTVJSEi4uLmpZV8Xf6e7du4wZM4bAwEDGjx+vlnXD/SEPr1+/rrb16Yu7d+8ya9Ys/Pz8GDVqFJs3byYmJoaYmBgUCgWSJBESEsLMmTNRKpWYmpoCcP36dWJjY3F1dWXu3LlMmTIFd3d3mfdGfjqddA0MDAgKCuLLL7/k9u3bLF26FE9PTywtLenYsSPR0dFYWVnRoEEDvvzyS8zMzPj222/54YcfOHLkCMeOHauUSG/fvs2XX37JvHnzsLCwYNeuXSiVSnbs2MG7777L9evXadWq1SNxXLp0idmzZ+Pj40Nubi5xcXEkJiYyfPhwhg8fzhtvvMG5c+dwdXVl2rRplYbRu3jxIsOGDWPWrFnaKDKtS0pKwsnJSW3rO3/+PNOmTaOgoIC2bdsSHBzMwIEDGTt2rOpkrykXFxeuXLmipkj1x969e8nMzGTDhg3k5eWxcuVKEhMTGTRoELdu3eLgwYMEBgZiaGhI586d2b59OwBDhw6lqKgIMzMznJycRML9L52u0zUyMsLZ2Zlff/2V0NBQ5syZQ2ZmJnv27MHU1JRt27bRvHlzVeL84IMPiImJYeLEiXz77bdERETw6quvAvenQP/qq69UCRfg6NGjBAQEANC7d29OnjxZZRzPP/88Pj4+HD9+nLNnz+Lj44O1tTWXL18mLy+P9PR0HB0dMTIy4qeffqJp06aq78bGxrJ//35efPFF3nvvPb0bUPr69es4OzvXej1Xr15l2rRpvP/++8yfPx8/Pz8AFi9eTHx8PH379uXEiRO12oa40q3a8OHDsbW15eWXX+bbb78lOTkZExMTbGxssLCwoGHDhhgaGlJSUkLr1q0ZPHgwgwcPpmfPnpw7d47Dhw/TvXt3uXejztDppAv3h6YLDg7G0NCQd955hw4dOvDJJ5/wxRdfMHr0aBITEykuLmbs2LEsWLCAVq1a0blzZzp06EBoaKhqkr5jx47h6elZKSEWFhaqxr61tLQkMzPzsXFIksS2bduwsLCgQYMGdOvWjbS0NFasWEHbtm2xtLSkadOmmJubV/pely5dWL9+Pbt27aKsrIwDBw5ooJTkk5ycrJYrXUmS6NWrF3v37qVbt26q9+3t7fnuu+/47rvvaNasWa224ezsXG96RVVXfn4+O3bs4I8//sDAwIB79+5x5MgRVScXSZLIycnh+PHjdOzYkeLiYjIyMmjYsCFOTk6qXoeCjlcvXLx4kVu3bjFt2jTatGlDeno68+bNw8nJicDAQIYPHw7cP2BSU1P55ptvMDExUT2hzs3NVT1IGz58OBs2bGDFihVMnjwZuD/Ic1FREXA/AT+pOZGBgQH/+te/+Prrr/nPf/5DZGQk8+fPp2nTpixbtoz169fz8ssvP/K99u3bq26LO3XqRFJSklrLSG6FhYVqaSrm7u6OlZUV7du3Vw1yM3/+fAASEhLYt29frZN748aNuXfvXq1j1UcFBQX89ddfmJqa4unpiVKpxMbGhvLycjw8PEhKSsLS0hJnZ2fV8wsrKyuSk5PJzMwkPT2d7t2788orr8i8J/LT6Svdtm3bMmXKFBwdHfnll1/417/+RefOnfnjjz9wcXHh+++/B+6f+D4+Pvz666+UlZUxd+5cOnXqxODBgys9TQ0JCcHa2pqlS5cC95NgRZVCfHz8Y0/qJUuWsHHjRgDy8vKwsLAgLy+PS5cuUV5eTmxs7GO7mL7zzjvEx8dTXl7O3r176dChg7qKR+80aNAAT09Ptm3bVunl7e2NoaFOH8p1nq2tLW+99ZZq5LHly5fTsWNH2rRpQ3FxMQUFBQQGBjJ06FDeeecdgoKCKC8vZ/Xq1YSHh+Pq6kpwcLDMe1E36PSVrrGxMU2aNOHq1auq/684+crKyrh79y4JCQmqKgJTU1MmTZrEoEGD6NGjB1OnTn1knYGBgezatYutW7fi7+9PYGAgGRkZHDx4kIiICBISEtiyZQszZ85Ufefll19m6tSprF27Fg8PD3r37o2FhQXvvvsuaWlp+Pj4MGzYsCr34d133+XNN99EkiQGDBigqqsUHmVoaEhcXBxDhgyp9H5iYqJMEdUPqampNG/enMaNG2NsbExpaSnr16/n5MmTJCcnY2pqSkpKCn/88QdeXl4sXryYFStWcOjQITIzM0lJSeHIkSNPbMpZn+h8N+D8/Pwqb1ny8vLo0aMHPXv2pGnTpmzZsgWFQoGrqyuDBg3i3LlzHD16lNu3b/PBBx/Qq1evKrebm5vLkSNHeO6557Czs1P7flWHLnaVHDJkCCNGjGDgwIG1Xld2djZTpkwhPDy80vuhoaF8/fXXta5euH37Ni+++CK3bt2q1Xp0WVXnWVRUFGZmZjz77LOsXr0aOzs7FAoF3bp1o3Xr1uTk5BAVFcXt27d5/fXXCQgIoGHDhgDcvHmTmTNn0rRpU+zt7R/bHFIXj+2a0vmkW5/o4oH5uKRbk84kSqWSgoKCRx5GqotIumLsBW0QFWGC1lV0Jjl79izBwcFkZ2dXudx7771HQECAqm7e0NCwyoT78HKP87TLCYImiaQraF1FZ5Jp06bRu3dv4uLiHlnmwY4pycnJj20/q+7lBEHTRNIVNO7h2R+q6kzysKftmKLO5Wo6S4UgVIfOtF5wcXHB0dFR7jBkpa4xDLSpefPmVVYfPNyZ5GEPd0yp6mpY3ctlZmbSvHnzp9uxekySpKeeZUOpVIrmfA/RmaSrrZ5CkyZNIigoiMGDBz9xudLSUjw8PLh48WKt+/zrs5YtW1Y559bDnUmGDh1a6fOn7ZiizuVSUlJUAw/VV3Jd3OjiBUVNiZ+gB9y9e5fNmzdX6mb6OMbGxrRo0UI1oplQtVatWpGamlrpvao6kzzsaTumqHO51NTUKgc0qk+Sk5ORJOmxr+TkZKytrSkuLn7icpIkoVQqadWqFadOnfrbZetT92uRdB+wfft2nn/++afuwz969GjCwsI0HJVuc3NzIy0trdJ7L7/8Mps2bSIwMBClUomDg4OqS28Ff39/wsPDmT17Njt27KB///7cunWLzz777G+XS0hIeKr1PUwk3b+3fv16hg8fjomJyd8ua2BgIM6RKuhMO11teOmllxgxYgTjxo17quUzMzNp27YtN2/epHHjxhqOTjfdunULLy8vzp8/X+3Zdh/umFJeXs6qVase6QzztB1Y/m650NBQ3n///Ud6vAn/07VrVxYsWPDUM4HEx8fj7+9PcnKyqNv9L5F0/ysnJwc3NzdSU1Or1fh+0KBBjBs3jtGjR2swOt0lSRKtWrVS9dWvjfLyckpLSzEzM1NTdP9z7949vL29uXbtGra2tmpfvz64cuUKffv2JTU1FSMjo6f+XqdOnViyZIno4v5f4qfnv8LDw/nHP/5R7d5O4vbpyQwMDBg6dCh79uyp9bqMjIw0knDhflfXzp07i4T7BGFhYYSEhFQr4YI4Rx4mku5/hYWF1ehqddiwYRw+fJicnBwNRKUfJk+ezOrVq/n999+5du1anWkPK0kS6enp7Ny5k9mzZ/P666/LHVKdJUlSjc+RUaNGsWnTJkpLSzUQme4R1QtAeno6HTt2JD09XTVQR3WMGDECf39/MVboExw/fpxvvvmG06dPo1Ao6NixI66urlhaWmJlZVXly9LSskYTGSqVSvLz81EoFOTk5KBQKCq9cnNzSU9PV7XV9fb25tVXXxVDDz7BmTNnGDFiBImJidWum4f7HWI+++wzBg0apIHodItIusD333/P2bNnWb16dY2+Hx4ezo8//qh3sz5oSk5ODmfOnCE5OZns7GyysrIq/ZuTk0N2djYKhaLS7LJPy8DAAAsLC2xsbLC2tsbGxgZbW1vVv7a2tjg4OODt7Y2jo2ONkkh98+GHH2JsbMy8efNq9P1FixZx6tQp1Uwt9ZlIukD37t2ZM2dOjYcfvHfvHo6Ojly8eBEHBwc1RycI8lIqlbRs2ZKdO3fi5eVVo3Xcvn2b9u3b1/huUp/U+zrda9eucePGDV544YUar6Nhw4YEBASwYcMGNUYmCHXD0aNHMTc3r3HChftz2fn4+BAREaHGyHRTvU+669atY8SIETWqO3yQeEIr6KuaPkB7WGhoqDhHENULeHp68tNPP+Hr61ur9ZSWluLo6MjJkydxc3NTU3SCIK+ysjIcHR05duwYrVu3rtW6cnNzcXV1JSUlpcqu3/VFvb7SjYuLIz8/nx49etR6XcbGxowYMYJ169apITJBqBsOHDiAm5tbrRMu3B/drW/fvmzZskUNkemuep10w8LCGDVqlNq6J4oqBkHfqKtqoYI4R+px9UJF99TNmzfj7e2tlnUqlUpcXV3Zs2dPrbu8CoLcioqKcHBwID4+Xm3DPRYWFuLo6EhCQoLsE73Kpd5e6R4/fhxTU1O6dOmitnUaGhoycuTIev9LLuiHXbt2qdoyq0ujRo0YPHiwamjP+qjeJt2K2yZ1N4yvuH2qpzcQgh5Rd9VChfpexVAvqxfKyspwcnLiyJEjuLu7q3XdkiTRrl07fv/996caDF0Q6qL8/HycnZ1JSkrC2tparesuKSnB0dGR06dP18uZOurllW5kZCROTk5qT7ggBm4W9MP27dvx8/NTe8IFMDExISgoqN629KmXSVdTt00VRo8ezfr162s0boAgyO3LL79k7dq1jB49mtu3b7N58+ZHlqmYb66mnvbC5OGRyUpLS+vMKHU1Ve+SbnFxMVu3bmXkyJEa24aHhwfNmzfnyJEjGtuGIKhbZmYmp0+fZvv27URFReHj48PWrVu5detWpeXKysoIDAykuLhYNaTp559/Xq0xk3v16kVmZiaXLl2q9P7ly5fp27cv/fv3JyQkhBkzZjB06FBcXFwICAhg6NChJCUlERwczI4dO7h58yaOjo7079+f/v3706VLF1auXFn7wtAgnZkNuLZee+01hg4dSklJCVZWVqxdu5YPP/xQY9ur+CXv27ev6r0JEybg6OjIl19+yezZswFU/wqC3OLj4/n2228pLi7GxcWF8+fPExYWRlFRkaq1Qd++fSkrK8PIyIg///yT33//nZ9++gljY2MaNGigmpDy7wY6NzIyUrX0mTNnjur9du3asXbtWj799FN+/PFHrl69SmpqKt9++y2TJ0+mSZMmtG7dmp9//plt27ZVmom7c+fO9O3bl9zcXI2Uj7rUmyvdmTNn8sMPP/DHH39QWlqq8QGrR40axebNmykpKan0/vLly2t9ayYImtCnTx/s7OwoLi7mtddeo1mzZtjZ2RETE0NkZCTl5eXMmDGDe/fuAXDu3DmmT5+u+v6sWbMYPHgwX3/99VNtr6qWPgYGBmzcuJFhw4ZhaGjIokWLSEpKoqysjIKCAj7//HN2797Nrl27CAgI4MSJE3Tp0oXZs2dz6dIlLl68SEJCAlevXlVr2ahTvUm6bm5uWFlZsW3bNkaOHEnTpk01uj0XFxc8PDz4z3/+U+l9T09P/vjjD41uWxBqIi8vj8uXL5OcnIyDgwPOzs7MmzePV155hVOnTjF58mSioqJo2rQpJ06cID8/nxMnTqi+/8UXX7Br1y7+7//+76m298wzzyBJEqdPn1a9V1JSwvfff8+XX36Jg4MDBgYG/Prrr1y6dIlly5aRkZFB7969iY2NZdOmTWzZsoWQkBASExMJCQnBzs4Oc3NzFi5cqPbyUZd6k3Th/gwB5eXlfPTRR1rZXlUPC958802WLVumle0LQnUcOHCAhIQETExM+Prrr5k7dy7u7u7cuXMHpVLJhAkT8Pf3Z8CAAWRlZZGRkYGXlxf9+/dn9erVfPjhh/Tv358bN2481faqaumzfPlymjRpwsqVK+nZsycGBgYsWLAAX19fli1bhru7O40aNeKLL76gV69evPfee8ycOZPVq1ezevVq5syZQ+vWrQkKCtJQKdVevUq6UVFRqtkEtCE4OJidO3dSWFioes/e3h4PDw8iIyO1EoMgPK3hw4fTsmVLxo0bx2effcbSpUspKyvj5MmTnDp1CrjfjXfGjBl4e3vzzDPP8OOPP2Jra0tiYiKxsbG0bNmyWq0LRo8ezbp161QtfV5//XWGDx+u+rxfv36Eh4dz+fJl1q9fT69evYD7LZAOHDhAhw4daNGiBS+//DIvv/wynp6eWFlZ0b9/fzWWjHrVm6SbnZ3NkSNHaNy4sda2aWdnR/fu3dmxY0el9999910OHz6stTgE4Wn88ccfXLhwgaNHj7J48WK+/fZbwsLCGD9+PGvWrKGoqIglS5YQEhKCo6MjL730Ei+//PIj66nOAFIdOnTA1taWqKioSt+dNGkSx44d45lnniE5ORlXV1f++c9/qqouwsPDVdtu3LgxHh4eeHh46MRszvWm9UJ4eDgDBgzgzJkzWt3uqFGjCAsLq9REzdvbm969e2s1DkH4O5cvX2bcuHF06tQJFxcX2rRpQ3BwMDExMezdu5eQkBB++eUX7Ozs2LdvH+bm5nTo0IHIyEjVleWlS5eeuk63QsXg5n369AHuN+tcuXIly5Ytw9HRERMTE1JSUli0aBGhoaEkJCRgYWGBlZUVAImJicyaNQuAGzduMG7cOPUViiZI9USfPn2kzZs3a327CoVCatq0qaRQKLS+bUF4WkqlUmrfvr0UExMj/fDDD9KmTZukUaNGSX/++adqmd9++03avXu3JEmSNHDgQKm4uFhKS0uTRo4cqVpm8uTJUlxcXLW2fePGDcnGxkYqLi6WJEmSkpKSpMLCQkmpVErjx4+XwsLCpPLycmnz5s1ScHCwFBkZKZ06dUr1/QEDBkiSJEmXL1+WXnzxRSkpKammxaAV9WLshZs3b+Ll5UV6ejpmZmZa335gYCABAQFMmjRJ69sWhKdx7tw5VceD6gwCJUkSJSUlldrL1kTPnj35+OOPGTx4cK3WowvqRZ3uhg0bGDp0qCwJF/73sEAQ6qqKAf2rO+qegYFBrRMu1K+Rx+rFlW63bt344osvGDBggCzbrxi4+cqVKzRv3lyWGAThcSRJws3NjW3bttG5c2dZYsjIyKBdu3akp6fTqFEjWWLQFr2/0r127RrJycn069dPthgaNWrEkCFD6vXAzULddfz4cRo1akSnTp1ki6F58+Z069atXkzRrvdJNywsjODg4FpPsV5b9en2SdAtmhrQv7rqyzmi19ULkiTh6enJzz//TM+ePWWNpb4P3CzUTRUD+kdHR9OmTRtZY8nNzcXFxYWUlBQsLS1ljUWT9PpKNy4ujoKCAp5//nm5Q6n3AzcLdVNkZCTOzs6yJ1y4P0V7//79qxy/V5/oddJV9xTrtVVfbp8E3aHpAf2rqz6cI3pbvVDxRHbr1q1qnfG3NsrLy3FxcWH//v20b99e7nCEeq64uBhHR0fOnz9PixYt5A4HgHv37uHg4MDly5ext7eXOxyNqBuXgBpw7NgxGjZsKFsTmKo8OHCzIMhtz549eHl51ZmEC9CwYUMCAgL0uqWP3ibdsLAwQkNDZX8i+zAxRbtQV9S1qoUK+l7FoJfVC3XpiezDJEmibdu2rFu3jmeeeUbucIR6qqCggBYtWnDt2rU6NzJXaWkpjo6O/Pnnn7Rs2VLucNROL690Dx06VGeeyD7MwMBANfKYIMhl+/bt9OzZs84lXABjY2O9bumjl0m3rt42VaiYol3Xp5IWdJcunCNr166VOwyN0LvqheLiYhwcHIiLi6tTDwge1qlTJ5YsWYKfn5/coQj1TE5ODm5ubqSlpWl8rsCaUiqVuLi4sHfvXjp27Ch3OGqld1e6u3fvplOnTnU64YL+PywQ6q6KAf3rasKF+zNI6GtLH71LunX9tqnCqFGj2LRpE6WlpXKHItQzunKOVMwooWc34/qVdAsKCtizZw8jRoyQO5S/5ebmRps2bdi/f7/coQj1SHp6OmfOnOHFF1+UO5S/1bVrV4yMjPjzzz/lDkWt9Crpbtu2DV9fX2xsbOQO5amIKgZB2+Qe0L86qpqiXR/oVdJdu3atTtw2VQgJCWHHjh3cu3dP7lCEemLdunU6dY5UtPSpmKJdH+hN0s3OziY6OpqhQ4fKHcpTs7e3x8fHh507d8odilAPXL9+naSkJF544QW5Q3lqHh4eNG/enCNHjsgditroTdLdtGkT/v7+dfqJbFX08fZJqJvWrVvHiBEjZB/Qv7r07RzRm3a6ffr0Yfr06QwbNkzuUKpFoVDQsmVLUlJSsLCwkDscQY95eXnx73//G19fX7lDqZaUlBS8vb25desWJiYmcodTa3pxpXvz5k3Onz/PoEGD5A6l2qysrOjTpw9bt26VOxRBj124cIG8vDx69OghdyjV5uLiQvv27dm7d6/coaiFXiTd9evXM2zYMLVMBS0HMRaDoGlhYWGMHDmyzgzoX136VMWgF9ULzz77LF9++SX/+Mc/5A6lRu7evYujoyOJiYk0a9ZM7nAEPSNJEm3atGHjxo107dpV7nBq5M6dO7i7u3Pz5k0aN24sdzi1ops/ew+4evUqqamp9O3bV+5Qaqxx48a8+OKLbNq0Se5QBD108uRJGjRogLe3t9yh1JidnR3PPfccO3bskDuUWtP5pLtu3bo6McV6benT7ZNQt9SVKdZrS1/OEZ2uXpAkiQ4dOrBixQqdfEDwoIr5qs6ePYuzs7Pc4Qh6ory8HGdnZw4dOkS7du3kDqdW8vPzcXZ25saNG1hZWckdTo3p9JXuuXPnuHfvXp2YYr22TE1NCQwMZP369XKHIuiRw4cPY29vr/MJF8Dc3FwvpmjX6aRbMcW6rt82VdCX2yeh7tCVEcWelj4Mbq5z1QtlZWVER0fj5+eHm5sbO3bsoFOnTnKHpRbl5eU4OTlx+PBhEhIScHd3x93dXe6wBB1z9+5dfv/9dyZOnIiDgwNnzpzBxcVF7rDU4t69ezg6OnLx4kUyMzNxcHDQuRY/Onele/v2bcaMGcOxY8do0qQJnp6elJSUyB1WreXn55Oenk5ISAhhYWEsWbKEq1evyh2WoIPy8/P59NNP2bt3Lx06dMDc3Jz09HS5w6q18vJyjI2NCQgIYMOGDXz66adER0fLHVa16VzSdXBwICsri99++43g4GCGDRvGd999J3dYtXbp0iWeffZZunbtSlhYGElJSbi5uckdlqCD7O3tKSgoYM2aNbz44ov07NmTiIgIucOqtcOHD9O5c2cGDhyoOkd0cbZgnateAGjbti3Z2dl4enpib2/PH3/8gbGxsdxh1dqWLVt47bXXMDIyIjs7G4VCQaNGjeQOS9BB7dq1Iy0tDUdHR8aNG8enn34qd0hq8cUXX7BmzRqys7MpLi4mLS0NS0tLucOqFp270oX7TzELCgpwcXFh7dq1epFwAQIDA1mxYgUKhQJjY2ORcIUaa9SoEUVFRbz66qt6k3ABZs2axauvvkpJSQlKpVLnEi7o6JVuv379KC0tJTIyEiMjI7nDUbtVq1axbNkyjh8/Lncogo4aN24cTZo04ccff5Q7FI14//33WbduHTdv3pQ7lGrTatKVJIn8/Hyys7PJysoiOztbdRtd05HhmzZtio2NDba2ttjY2GBjY4O1tXWd7aFWXFys2u+HX5mZmbUqCwsLi0pl8WCZ2NjY0LhxY71pXqdvioqKHjkvKl5ZWVnk5ubW6LgwNDTEwsLikWPhwVejRo3q5HGhVCrJzc19pExyc3NrNFmlgYFBlWVhaWmp1Ys3jSTd1NRUTp06xenTp4mNjSUpKUmVXM3MzLC2tsbKykr1srCwqFGSlCSJu3fvolAoyMnJUf2bl5dHkyZNsLa2xt7eni5duuDj40PXrl3x8vLSWkIuLS1l165d/Pnnn8TGxhIbG0tOTk6lfa94WVpaYm1tXeOyUCqVFBQUoFAoVK/c3FxycnJUZWNkZESnTp3w8fHBx8eHwYMHY2trq4E9F56kqKiIiIgI1Tly5swZ/vrrr0fOi4rjouIcqUliUCqV5Ofnq46HB4+PivPF1NSULl260LVrV3x8fBgyZIjWxnaWJImEhARiY2NV+SItLY3s7OxK5/GDZWJubl6j0dIqLvoqzoeK/S8oKMDCwgJra2ucnJzw9vZW5QsPDw+1/yCpNelKksRbb73FunXr8PHxoWPHjnh5eeHm5qYqMG0MQqxUKsnLy0OhUHD79m3i4+O5cOECZ8+excTEhN27d2u8q21hYSF9+vQBoGfPnnh5eeHl5UWLFi1ku6pQKBTEx8cTFxfH2bNnOX78OAcOHMDLy0uWeOojhUJBjx49aNasGd27d8fLy0v1QFiu4yI7O5u4uDji4uI4c+YM58+fJzo6WuOtZ4qKihg+fDjnzp2ja9eueHp64unpibOzs+oHRxsXSGVlZeTl5ZGTk8PNmzeJi4sjPj6e06dP065dO7Zv367Wkc3UmnR37NjBRx99xNatW2nSpIm6Vqs2kiTxzTffkJ6ervHutj/99BObN29m9erVdfLWDWDlypX8+eefYgB1LZo7dy7x8fF1upnjggULyMvL45dfftHodubPn8+hQ4f4+eef6+TD8LKyMt5++226dOnC7Nmz1bZetbZe2LRpE6NHj66TCRfu1+lMnjyZPXv2UFRUpNFtbd26laCgoDqbcAGGDRvGoUOHxGzEWrRt2zZGjBghdxhPNGLECHbs2IFSqdTodsLDw5k4cWKdTLgADRo0YNKkSYSHh6t3vepakSRJREREsGfPnlqva+LEidy9e1e13rKyMtUfpri4mG3bttV43TY2NnTo0IHIyEj8/f1rHWtVSkpKiIqKYtGiRRpZv7pYW1vToUMHoqKiGDBggNzh6L2srCwSExPp1q2b3KE8UcuWLbGwsODcuXMaG4M3IyODhIQEtQxWpcl84ePjQ0ZGBsnJybi6utY6VlBj0s3MzESSJJycnGq9rlWrVgH3+5CPGTOGwMBAxo8fX+v1VujYsSOXLl3SWNJNSUmhWbNmapuZ2M/PD3t7+0rvJSYmEhsbW+t1u7u7c/XqVZF0teDq1au0atVKbVd2mjwu2rVrx9WrVzWWdC9fvoyHh4daykKT+cLQ0FCVL+pc0k1KSlLroBrnz59n2rRpFBQU0LZtW4KDgxk4cCBjx46t9VxoLi4uXL9+XU2RPurGjRtqfVBnampKr169Kr13+/Zttay7RYsWJCUlqWVdwpPp0nHh5OTEjRs31LKuqiQlJam1LDSZL5ydndV6jqitTvf69etq+SW4evUq06ZN4/3332f+/Pn4+fkBsHjxYuLj4+nbty8nTpyo1TacnZ01mnSTkpLUcsX/ID8/v0ovdV0tafoHSPif69ev68xx4eTkpNHj4tq1a2pJutrIF05OTly7dq3WsVZQ25Wuug4oSZLo1asX3333HYaGhqpWBvb29nz33XecOHGi1kO5ubi4aPTqTt2/4q6ursyZM6fSe+pqX+vi4kJycrJa1iU82Y0bN2jTpo3a1qfp4+LIkSNqWVdVrl+/zrPPPlvr9WgjX7i6uqp1+ne1Jd2UlBS1jPjj7u6OlZUV7du3x8PDA7jftAQgISGBffv21Tq5Ozs7k5KSUutYHyc5OVktD0uuXr3K77//jrOzc5VJfPbs2QwYMKBWUxW1aNFCJF0tSU5Opnfv3rVej7aOC02fI4GBgbVejzbyhZOTk1rPEbUl3ZKSklrXnVRo0KABnp6ejzTVCA0NrVFPlIeZmppqdAzesrIytXQCcXV1Zfr06Rw8eJB27dpx584dTpw4wTvvvEN5eTmlpaW1HhTH1NSUsrKyWscq/L3S0lKdOi5KS0trHevjlJWV6VS+UGdZ1MkBCgwNDYmLi2PIkCGV3k9MTJQpInmYmJhgYmLCzz//zPfff4+ZmRk7duzg/PnzSJJEaGgoL730ktxhClomjovKdC1f1MmkW1ZWhpeXV5W/XJpusF3X7N+/H1NTU95//3169erF8OHDmTFjhtxhCTITx8X/6Fq+qJNJ18rKStX27kG6PiFddaWlpTFnzhzWrVuHgYEBy5cvJyYmhoMHD1JUVEROTg4TJkxg+vTpcocqaJE4LirTtXxRJ5OuoaEh5ubmcochOycnJ7Zs2YKNjQ0An332mcwRCXWBOC4q07V8ofGZI/Lz8xkzZgyjRo1i0qRJj32A9d577xEQEMD333//xPWpezlt+vXXXwkKCiIoKIj+/fvz4YcfVrncg7FXnFh/t9yT1MWyECrLzMxk2LBhT1ymvhwXmZmZ/OMf/3js57qeKzSedDdv3syUKVNYt24ddnZ2HDp06JFldu3ahVKpZMeOHSQnJz+2Uba6l9O28ePHEx4eTnh4ON27d2fMmDGPLFNfykL4n9zcXKZNm0ZhYeFjl6lPx8WcOXMeOyCVPpSD2pKukZFRlc0qJkyYoGqbmJ2dXWXj7aNHjxIQEABA7969OXnyZJXbUNdypaWlGh2n08DA4IkV+Ldu3SIrK4vOnTs/8pm2y6K8vLxOj4SmTwwMDKqc/cHIyIiffvrpiWN16Ntx8bh8ER0dTaNGjbCzs6vye9ouB1B/vlBb0nV2diY9Pf2xn586dYq8vDx8fHwe+aywsFA1cIelpSWZmZlVrkNdy928eVPt3TEf5ODgQEZGxmM/X716NePGjavyM22XRUZGBg4ODk/eIUEtHBwcuHPnziPvN23a9G/rJPXtuHBxcXlkfrOSkhK+//57Pv7448d+T9vlAPcfXKqzh6nakm7r1q0f24NFoVAwa9YsFi5cWOXnjRs3Vt1OFBYWPnb+I3Utl5KSotFR8d3c3EhNTa3yM6VSydGjRx/bW0iOslBHT0Lh77m5udW4l5e+nSOtWrV6pJfXkiVLGD9+/BOnCtJ2OcD9smjduvXf79RTUlvSfVyiKSkpYerUqfzf//3fY68uO3XqpLqsj4+P1/hyycnJtGrV6ul2rAbc3NxIS0ur8rMTJ07g7e392Fs3bZdFamqqxqdlEe5r1arVY4+Lv6Pt4yItLU3jSffhsoiKimL16tUEBQURHx/P+++/X+24NbFcSkqKWvOF2ioq3NzcquyfHBYWRlxcHIsWLWLRokX06NGDsrIyZs6cqVrG39+fwMBAMjIyOHjwIBEREdy6dYt///vflQb0qGq5hIQEtmzZ8rfre1BqaqpaBx55WMuWLR97RRMZGclzzz0H8NSxa7os3N3d1bn7wmO0bNnysXdAD6orx0WXLl1qv9OPUdWV7pYtW1T/HRQUxNSpU5k/f76s5QD3y2LkyJFq23e1zZGmVCqxsrIiKiqqRqP65ObmcuTIEZ577jns7OwoLy9n1apVvPLKK09c7mnX96DQ0FDeffddjXWVLCgooHnz5ly+fLlGFfDaLIsJEyYwZcoUgoKCqh2nUD03btzg+eef5/Tp0zV6SKXN4yIgIICFCxeqhkpUt/T0dDw9PTl37ly1zxFtloMkSTzzzDNERUWprYpBrRNThoSE0K1btyqbQlVXxcAdZmZmaojsf/Lz83n22WdJT0/X6FxuXbt25ZNPPqnVSE8VNFUWxcXFdOnShYSEhCcelIJ6SJJEy5YtWb16tWpErNrQ1HGhUCh47rnnuH37dq0HznmSLl268Pnnn6vu/GpKU+UAcO7cOaZNm8aVK1fUtk61ttMNCgpiw4YNahmRx8jISCOFuHHjRnr16qXxyTOHDh3K7t271bIuTZVFVFQUHTp0EAlXSwwMDHjppZfYtWuXWtanqeNi37599OnTR6MJF2D48OH89ttvtR4fQVPlIEkSa9asYfjw4Wpdr1qvdMvKylSV4D169MDT0xMvLy9atmyJubm5WoZZq47CwkJu375NfHw8cXFxnD9/nsTERPbv30/79u01uu2UlBSeeeYZxo4dS69evejYsWOdmCW5tLSUhIQEzp49y3fffcd3331HSEiI3GHVG/Hx8fTu3ZupU6fy3HPP0aFDB40nt6dRXFzMlStXOHXqFD/88APr1q2jX79+Gt3mX3/9xcCBA8nOzubZZ59V5QsnJyesrKy0OktwaWkpubm5pKWlceHCBS5cuMCpU6do2LAhBw4cwNLSUm3bUmvShfu/DidOnODUqVOcPn2a06dPk5yczN27d7G0tMTa2hpra2usrKywtLRU/VuTuk9Jkvjrr79QKBSPvHJycpAkiebNm9O5c2d8fHzw8fGhd+/eapsw8u8kJiaycOFCTp8+zYULF3B0dMTV1bXSvj/4sra2rnFZKJXKSmWRk5Oj+jc3N5fc3Fxu3bpFQkICrq6ueHt7M378eAYOHKiBPReepOLBcmxsLJcuXcLFxQVnZ2fV3//h48LKygoLC4saHxd5eXlVniO5ubkoFApu3rzJtWvXaN26Nd7e3kyZMgVfX18N7HnV8Z08eZLY2FhOnz5NbGwsaWlpKBQKGjVqpDovHiwLc3NzjIyMqr2t8vJy8vPzqyyLivzUokULunbtio+PD97e3nTv3l3tHanUnnQfp7S0lJycHLKzs8nOziYrK0v139nZ2VX21Hka5ubm2NraYmtri42NTaVXo0aN6kxvq7KyMi5dukRycvIjZZCVlUVOTg5ZWVkoFIoal4WFhQXW1tbY2NioyuTBcnFwcMDT07NOXHEL95WUlHDx4kVSU1NVx8KDx0V2drbqB7Qmt+EGBgaqi52K4+LBf21sbGjRogWenp40bNhQA3tYM0qlkvz8/CpzRW3KwsrKqspcYWFhobU7ca0lXUEQBEELA94IgiAI/yOSriAIghaJpCsIgqBFIukKgiBokUi6giAIWiSSriAIghaJpCsIgqBFIukKgiBokUi6giAIWiSSriAIghaJpCsIgqBFIukKgiBokUi6giAIWiSSriAIghaJpCsIgqBFIukKgiBokUi6giAIWiSSriAIghaJpCsIgqBFIukKgiBokUi6giAIWiSSriAIghaJpCsIgqBFIukKgiBokUi6giAIWiSSriAIghb9P0pCESNs4qIAAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'纹理': {'清晰': {'密度<0.3815': {'Y': ('否', 2.0, 0.0), 'N': ('是', 7.0, 0.0)}}, '模糊': ('否', 3.0, 0.0), '稍糊': {'触感': {'软粘': ('是', 1.0, 0.0), '硬滑': ('否', 4.0, 0.0)}}}}\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import matplotlib\n",
    "from collections import Counter\n",
    "import treePlotter as tp\n",
    "\n",
    "matplotlib.rcParams['font.family']='SimHei'  # 用来正常显示中文\n",
    "plt.rcParams['axes.unicode_minus']=False  # 用来正常显示负号\n",
    "decisionNode = dict(boxstyle=\"sawtooth\", fc=\"0.8\")  # 定义分支点的样式\n",
    "leafNode = dict(boxstyle=\"round4\", fc=\"0.8\")  # 定义叶节点的样式\n",
    "arrow_args = dict(arrowstyle=\"<-\")  # 定义箭头标识样式\n",
    "\n",
    "ds=np.loadtxt(open('watermelon_3a.csv',encoding='utf8'),dtype=str,delimiter=',')\n",
    "\n",
    "labels=ds[0][1:-1].tolist()\n",
    "#print(labels)\n",
    "labelProperties=[0,0,0,0,0,0,1,1]\n",
    "#print(labelProperties)\n",
    "classList = ['是', '否']\n",
    "ds1=np.concatenate((ds[1:,1:-1],np.ones(17).reshape(17,1)),axis=1)\n",
    "ds2=np.concatenate((ds1,ds[1:,-1].reshape(17,1)),axis=1)\n",
    "trees = createTree(ds2.tolist(), labels, labelProperties)\n",
    "tp.createPlot(trees)\n",
    "print(trees)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "19130f47",
   "metadata": {},
   "source": [
    "## 作业2\n",
    "试将4.4.2 节对缺失值的处理机制推广到基尼指数的计算中去。\n",
    "\n",
    "CART决策树使用基尼指数来选择划分属性。数据集D的纯度可用基尼值来度量：  \n",
    "$$\n",
    "\\begin{align*}\n",
    "Gini(D)&=\\sum_{k=1}^{|y|}\\sum_{k' \\neq k}p_kp_{k'}  \\\\\n",
    "&=1-\\sum_{k=1}^{|y|}p_k^2\n",
    "\\end{align*}\n",
    "$$\n",
    "属性a的基尼指数定义如下：  \n",
    "$$\n",
    "Gini\\_index(D,a)=\\sum_{v=1}^{V}\\frac{|D^v|}{|D|}Gini(D^v)\n",
    "$$\n",
    "\n",
    "于是，我们在候选属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性。\n",
    "$$\n",
    "a_*={\\underset {a \\in A}{\\operatorname {arg\\,min} }}\\,Gini\\_index(D,a)\n",
    "$$\n",
    "\n",
    "如果考虑到数据集中有缺失值，那么我们可以将基尼指数推广为：  \n",
    "$$\n",
    "\\begin{align*}\n",
    "Gini\\_index(D,a)&=\\rho \\times Gini\\_index(\\tilde{D},a) \\\\\n",
    "&=\\rho \\times \\sum_{v=1}^{V}\\tilde{r}_v Gini(\\tilde{D}^v) \\\\\n",
    "\\rho &= \\frac{\\sum_{x \\in \\tilde{D}} w_x}{\\sum_{x \\in D} w_x} \\\\\n",
    "\\tilde{r}_v &= \\frac{\\sum_{x \\in \\tilde{D}_v} w_x}{\\sum_{x \\in \\tilde{D}} w_x}\\,(1 \\leq v \\leq |V|)\n",
    "\\end{align*}\n",
    "$$\n",
    "\n",
    "下面进行编程实现。为实现方便，做如下假设：  \n",
    "1. 缺失值为字符'N'表示； \n",
    "2. 最后一列放置分类变量；\n",
    "3. 倒数第二列放置权重变量，每个样本的权重均为1.0；"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "id": "cbf929f3",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "import matplotlib\n",
    "from collections import Counter\n",
    "import treePlotter as tp\n",
    "\n",
    "matplotlib.rcParams['font.family']='SimHei'  # 用来正常显示中文\n",
    "plt.rcParams['axes.unicode_minus']=False  # 用来正常显示负号\n",
    "\n",
    "decisionNode = dict(boxstyle=\"sawtooth\", fc=\"0.8\")\n",
    "leafNode = dict(boxstyle=\"round4\", fc=\"0.8\")\n",
    "arrow_args = dict(arrowstyle=\"<-\")\n",
    "\n",
    "# 计算传入数据的Gini指数\n",
    "def calcGini(dataSet):\n",
    "    # 获得y中分类标签的唯一值\n",
    "    y_lables = np.unique(dataSet[: , -1])\n",
    "    y_counts=len(dataSet) # y总数据条数\n",
    "    y_p={}             # y中每一个分类的概率，字典初始化为空，y分类数是不定的，按字典存储更方便取值\n",
    "    gini=1.0\n",
    "    for y_lable in y_lables:\n",
    "        y_p[y_lable]=len(dataSet[dataSet[:, -1]==y_lable])/y_counts  # y中每一个分类的概率（其实就是频率）\n",
    "        gini-=y_p[y_lable]**2\n",
    "    return gini\n",
    "\n",
    "# 计算Gini指数的另一种写法\n",
    "def getGini(dataSet):\n",
    "    # 计算基尼指数\n",
    "    c = Counter(dataSet[:,-1])\n",
    "    ret=1 - sum([(val / dataSet[:,-1].shape[0]) ** 2 for val in c.values()])\n",
    "    return ret\n",
    "\n",
    "#划分数据集\n",
    "def splitDataSet(dataSet, i, value,types=1):\n",
    "    if types==1: # 使用此列特征中的value进行划分数据\n",
    "        subDataSet=dataSet[list(dataSet[:,i]==value)]  # 按照数据x第i列==value即可判断，不需要像《机器学习实战》书里写的那么复杂\n",
    "        subDataSet = np.array(subDataSet)           # 强制转换为array类型\n",
    "    elif types==2: # 使用此列特征中的不等于value的进行划分数据\n",
    "        subDataSet=dataSet[list(dataSet[:,i]!=value)]  # 按照数据x第i列==value即可判断，不需要像《机器学习实战》书里写的那么复杂\n",
    "        subDataSet = np.array(subDataSet)           # 强制转换为array类型\n",
    "    return subDataSet ,len(subDataSet)\n",
    "\n",
    "def getrho(dataSet, i):\n",
    "    numTotal=dataSet.shape[0]\n",
    "    w1,w2=0.,0.\n",
    "    for j in range(numTotal):\n",
    "        w1+=float(dataSet[j,-2])\n",
    "    NNSet=dataSet[list(dataSet[:,i]!='N')] \n",
    "    for j in range(NNSet.shape[0]):\n",
    "        w2+=float(NNSet[j,-2])\n",
    "    return w2/w1\n",
    "\n",
    "def getrv(dataSet,i,value):\n",
    "    NNSet=dataSet[list(dataSet[:,i]!='N')]\n",
    "    w1,w2=0.,0.\n",
    "    for j in range(NNSet.shape[0]):\n",
    "        w1+=float(NNSet[j,-2])\n",
    "        if NNSet[j,i]==value:\n",
    "            w2+=float(NNSet[j,-2])\n",
    "    return w2/w1\n",
    "\n",
    "# 计算Gini指数，选择最好的特征划分数据集，即返回最佳特征下标及传入数据集各列的Gini指数\n",
    "def chooseBestFeature(dataSet):\n",
    "    numTotal=dataSet.shape[0]              # 记录本数据集总条数\n",
    "    numFeatures = len(dataSet[0]) - 2      # 最后一列为y，倒数第2列为权重，计算x特征列数\n",
    "    bestFeature = -1                       # 初始化参数，记录最优特征列i，下标从0开始\n",
    "    columnFeaGini={}                       # 初始化参数，记录每一列x的每一种特征的基尼 Gini(D,A)\n",
    "    rho=0.\n",
    "    rv=0.\n",
    "    for i in range(numFeatures):           # 遍历所有x特征列\n",
    "        # i=2\n",
    "        rho=getrho(dataSet,i)\n",
    "        prob = {}                          # 按x列计算各个分类的概率\n",
    "        featList = list(dataSet[:,i])      # 取这一列x中所有数据，转换为list类型\n",
    "        prob=dict(Counter(featList))       # 使用Counter函数计算这一列x各特征数量\n",
    "        for value in prob.keys():          # 循环这一列的特征，计算H(D|A)\n",
    "            # value='是'\n",
    "            rv=getrv(dataSet,i,value)\n",
    "            dataSet1=dataSet[list(dataSet[:,i]!='N')] \n",
    "            feaGini = 0.0\n",
    "            bestFlag = 1.00001  # 对某一列x中，会出现x=是，y=是的特殊情况，这种情况下按“是”、“否”切分数据得到的Gini都一样，设置此参数将所有特征都乘以一个比1大一点点的值，但按某特征划分Gini为0时，设置为1\n",
    "            subDataSet1,sublen1 = splitDataSet(dataSet1, i, value, 1)  # 获取切分后的数据\n",
    "            subDataSet2,sublen2 = splitDataSet(dataSet1, i, value, 2)\n",
    "            if (sublen1/numTotal) * calcGini(subDataSet1)==0: # 判断按此特征划分Gini值是否为0（全部为一类）\n",
    "                bestFlag = 1 \n",
    "            feaGini += rho*(rv*(sublen1/numTotal) * calcGini(subDataSet1) + \n",
    "                            (1-rv)*(sublen2/numTotal) * calcGini(subDataSet2))\n",
    "            columnFeaGini['%d_%s'%(i,value)]=feaGini*bestFlag\n",
    "    bestFeature=min(columnFeaGini,key=columnFeaGini.get) # 找到最小的Gini指数益对应的数据列\n",
    "    return bestFeature,columnFeaGini\n",
    "\n",
    "def createTree(dataSet,features):\n",
    "    \"\"\"\n",
    "    输入：训练数据集D，特征集A\n",
    "    输出：决策树T\n",
    "    如下实现，参照了周志华西瓜书中图4.2描述的“决策树学习基本算法”\n",
    "    \"\"\"\n",
    "    y_lables = np.unique(dataSet[: , -1])  #获得分类特征的取值（去重）\n",
    "\n",
    "    #1、如果数据集D中的所有实例都属于同一类label（Ck），则T为单节点树，并将类label（Ck）作为该结点的类标记，返回T\n",
    "    if len(set(y_lables)) == 1:\n",
    "        return y_lables[0]\n",
    "    \n",
    "    #2、若特征集A=空，则T为单节点，并将数据集D中实例树最大的类label（Ck）作为该节点的类标记，返回T\n",
    "    if len(dataSet[0]) == 2: #这里2的含义是，只剩下分类变量以及权重变量\n",
    "        labelCount = {}\n",
    "        labelCount=dict(Counter(y_lables))\n",
    "        return max(labelCount,key=labelCount.get)\n",
    "    \n",
    "    #3、否则，按CART算法就计算特征集A中各特征对数据集D的Gini，选择Gini指数最小的特征bestFeature（Ag）进行划分\n",
    "    bestFeature,columnFeaGini=chooseBestFeature(dataSet) \n",
    "\n",
    "    bestFeatureLable = features[int(bestFeature.split('_')[0])]    #最佳特征\n",
    "    decisionTree = {bestFeatureLable:{}}        #构建树，以Gini指数最小的特征bestFeature为子节点\n",
    "    del(features[int(bestFeature.split('_')[0])])                  #该特征已最为子节点使用，则删除，以便接下来继续构建子树\n",
    "    \n",
    "    #使用beatFeature进行划分，划分产生2各节点，成树T，返回T\n",
    "    y_lables_split=dataSet[list(dataSet[:,int(bestFeature.split('_')[0])]==bestFeature.split('_')[1])][:,-1] # 获取按此划分后y数据列表\n",
    "    y_lables_grp=dict(Counter(y_lables_split)) # 统计最优划分应该属于哪个i叶子节点“是”、“否”\n",
    "    y_leaf=max(y_lables_grp,key=y_lables_grp.get) # 获得划分后出现概率最大的y分类\n",
    "    decisionTree[bestFeatureLable][bestFeature.split('_')[1]]= y_leaf # 设定左枝叶子值\n",
    "    \n",
    "    #4、删除此最优划分数据x列，使用其他x列数据，递归地调用步1-3，得到子树Ti，返回Ti\n",
    "    dataSetNew= np.delete(dataSet,int(bestFeature.split('_')[0]),axis=1) # 删除此最优划分x列，使用剩余的x列进行数据划分\n",
    "    subFeatures = features[:]\n",
    "    # 判断右枝类型，划分后的左右枝“是”、“否”是不一定的，所以这里进行判断\n",
    "    y1=y_lables[0] # CART树y只能有2个分类\n",
    "    y2=y_lables[1] \n",
    "    if y_leaf==y1:\n",
    "        decisionTree[bestFeatureLable][y2]= {}\n",
    "        decisionTree[bestFeatureLable][y2] = createTree(dataSetNew, subFeatures)\n",
    "    elif y_leaf==y2:\n",
    "        decisionTree[bestFeatureLable][y1]= {}\n",
    "        decisionTree[bestFeatureLable][y1] = createTree(dataSetNew, subFeatures)\n",
    "    \n",
    "    return decisionTree"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "95b406c0",
   "metadata": {},
   "source": [
    "**下面采用西瓜数据集2a（含缺失值，用'N'表示）**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "id": "77d12fb3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>编号</th>\n",
       "      <th>色泽</th>\n",
       "      <th>根蒂</th>\n",
       "      <th>敲声</th>\n",
       "      <th>纹理</th>\n",
       "      <th>脐部</th>\n",
       "      <th>触感</th>\n",
       "      <th>好瓜</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>N</td>\n",
       "      <td>蜷缩</td>\n",
       "      <td>浊响</td>\n",
       "      <td>清晰</td>\n",
       "      <td>凹陷</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2</td>\n",
       "      <td>乌黑</td>\n",
       "      <td>蜷缩</td>\n",
       "      <td>沉闷</td>\n",
       "      <td>清晰</td>\n",
       "      <td>凹陷</td>\n",
       "      <td>N</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>3</td>\n",
       "      <td>乌黑</td>\n",
       "      <td>蜷缩</td>\n",
       "      <td>N</td>\n",
       "      <td>清晰</td>\n",
       "      <td>凹陷</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4</td>\n",
       "      <td>青绿</td>\n",
       "      <td>蜷缩</td>\n",
       "      <td>沉闷</td>\n",
       "      <td>清晰</td>\n",
       "      <td>凹陷</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5</td>\n",
       "      <td>N</td>\n",
       "      <td>蜷缩</td>\n",
       "      <td>浊响</td>\n",
       "      <td>清晰</td>\n",
       "      <td>凹陷</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>6</td>\n",
       "      <td>青绿</td>\n",
       "      <td>稍蜷</td>\n",
       "      <td>浊响</td>\n",
       "      <td>清晰</td>\n",
       "      <td>N</td>\n",
       "      <td>软粘</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>7</td>\n",
       "      <td>乌黑</td>\n",
       "      <td>稍蜷</td>\n",
       "      <td>浊响</td>\n",
       "      <td>稍糊</td>\n",
       "      <td>稍凹</td>\n",
       "      <td>软粘</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>8</td>\n",
       "      <td>乌黑</td>\n",
       "      <td>稍蜷</td>\n",
       "      <td>浊响</td>\n",
       "      <td>N</td>\n",
       "      <td>稍凹</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>9</td>\n",
       "      <td>乌黑</td>\n",
       "      <td>N</td>\n",
       "      <td>沉闷</td>\n",
       "      <td>稍糊</td>\n",
       "      <td>稍凹</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>10</td>\n",
       "      <td>青绿</td>\n",
       "      <td>硬挺</td>\n",
       "      <td>清脆</td>\n",
       "      <td>N</td>\n",
       "      <td>平坦</td>\n",
       "      <td>软粘</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>11</td>\n",
       "      <td>浅白</td>\n",
       "      <td>硬挺</td>\n",
       "      <td>清脆</td>\n",
       "      <td>模糊</td>\n",
       "      <td>平坦</td>\n",
       "      <td>N</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>12</td>\n",
       "      <td>浅白</td>\n",
       "      <td>蜷缩</td>\n",
       "      <td>N</td>\n",
       "      <td>模糊</td>\n",
       "      <td>平坦</td>\n",
       "      <td>软粘</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>13</td>\n",
       "      <td>N</td>\n",
       "      <td>稍蜷</td>\n",
       "      <td>浊响</td>\n",
       "      <td>稍糊</td>\n",
       "      <td>凹陷</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>14</td>\n",
       "      <td>浅白</td>\n",
       "      <td>稍蜷</td>\n",
       "      <td>沉闷</td>\n",
       "      <td>稍糊</td>\n",
       "      <td>凹陷</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>14</th>\n",
       "      <td>15</td>\n",
       "      <td>乌黑</td>\n",
       "      <td>稍蜷</td>\n",
       "      <td>浊响</td>\n",
       "      <td>清晰</td>\n",
       "      <td>N</td>\n",
       "      <td>软粘</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>15</th>\n",
       "      <td>16</td>\n",
       "      <td>浅白</td>\n",
       "      <td>蜷缩</td>\n",
       "      <td>浊响</td>\n",
       "      <td>模糊</td>\n",
       "      <td>平坦</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>16</th>\n",
       "      <td>17</td>\n",
       "      <td>青绿</td>\n",
       "      <td>N</td>\n",
       "      <td>沉闷</td>\n",
       "      <td>稍糊</td>\n",
       "      <td>稍凹</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    编号  色泽  根蒂  敲声  纹理  脐部  触感 好瓜\n",
       "0    1   N  蜷缩  浊响  清晰  凹陷  硬滑  是\n",
       "1    2  乌黑  蜷缩  沉闷  清晰  凹陷   N  是\n",
       "2    3  乌黑  蜷缩   N  清晰  凹陷  硬滑  是\n",
       "3    4  青绿  蜷缩  沉闷  清晰  凹陷  硬滑  是\n",
       "4    5   N  蜷缩  浊响  清晰  凹陷  硬滑  是\n",
       "5    6  青绿  稍蜷  浊响  清晰   N  软粘  是\n",
       "6    7  乌黑  稍蜷  浊响  稍糊  稍凹  软粘  是\n",
       "7    8  乌黑  稍蜷  浊响   N  稍凹  硬滑  是\n",
       "8    9  乌黑   N  沉闷  稍糊  稍凹  硬滑  否\n",
       "9   10  青绿  硬挺  清脆   N  平坦  软粘  否\n",
       "10  11  浅白  硬挺  清脆  模糊  平坦   N  否\n",
       "11  12  浅白  蜷缩   N  模糊  平坦  软粘  否\n",
       "12  13   N  稍蜷  浊响  稍糊  凹陷  硬滑  否\n",
       "13  14  浅白  稍蜷  沉闷  稍糊  凹陷  硬滑  否\n",
       "14  15  乌黑  稍蜷  浊响  清晰   N  软粘  否\n",
       "15  16  浅白  蜷缩  浊响  模糊  平坦  硬滑  否\n",
       "16  17  青绿   N  沉闷  稍糊  稍凹  硬滑  否"
      ]
     },
     "execution_count": 91,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#读入数据\n",
    "df_data=pd.read_csv('watermelon_2a.csv')\n",
    "df_data"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "48336990",
   "metadata": {},
   "source": [
    "**在原数据集中增加一列权重，每个样本权重都为1.0。**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "id": "66bdd200",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>编号</th>\n",
       "      <th>色泽</th>\n",
       "      <th>根蒂</th>\n",
       "      <th>敲声</th>\n",
       "      <th>纹理</th>\n",
       "      <th>脐部</th>\n",
       "      <th>触感</th>\n",
       "      <th>权重</th>\n",
       "      <th>好瓜</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>N</td>\n",
       "      <td>蜷缩</td>\n",
       "      <td>浊响</td>\n",
       "      <td>清晰</td>\n",
       "      <td>凹陷</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>1.0</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2</td>\n",
       "      <td>乌黑</td>\n",
       "      <td>蜷缩</td>\n",
       "      <td>沉闷</td>\n",
       "      <td>清晰</td>\n",
       "      <td>凹陷</td>\n",
       "      <td>N</td>\n",
       "      <td>1.0</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>3</td>\n",
       "      <td>乌黑</td>\n",
       "      <td>蜷缩</td>\n",
       "      <td>N</td>\n",
       "      <td>清晰</td>\n",
       "      <td>凹陷</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>1.0</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4</td>\n",
       "      <td>青绿</td>\n",
       "      <td>蜷缩</td>\n",
       "      <td>沉闷</td>\n",
       "      <td>清晰</td>\n",
       "      <td>凹陷</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>1.0</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5</td>\n",
       "      <td>N</td>\n",
       "      <td>蜷缩</td>\n",
       "      <td>浊响</td>\n",
       "      <td>清晰</td>\n",
       "      <td>凹陷</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>1.0</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>6</td>\n",
       "      <td>青绿</td>\n",
       "      <td>稍蜷</td>\n",
       "      <td>浊响</td>\n",
       "      <td>清晰</td>\n",
       "      <td>N</td>\n",
       "      <td>软粘</td>\n",
       "      <td>1.0</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>7</td>\n",
       "      <td>乌黑</td>\n",
       "      <td>稍蜷</td>\n",
       "      <td>浊响</td>\n",
       "      <td>稍糊</td>\n",
       "      <td>稍凹</td>\n",
       "      <td>软粘</td>\n",
       "      <td>1.0</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>8</td>\n",
       "      <td>乌黑</td>\n",
       "      <td>稍蜷</td>\n",
       "      <td>浊响</td>\n",
       "      <td>N</td>\n",
       "      <td>稍凹</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>1.0</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>9</td>\n",
       "      <td>乌黑</td>\n",
       "      <td>N</td>\n",
       "      <td>沉闷</td>\n",
       "      <td>稍糊</td>\n",
       "      <td>稍凹</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>1.0</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>10</td>\n",
       "      <td>青绿</td>\n",
       "      <td>硬挺</td>\n",
       "      <td>清脆</td>\n",
       "      <td>N</td>\n",
       "      <td>平坦</td>\n",
       "      <td>软粘</td>\n",
       "      <td>1.0</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>11</td>\n",
       "      <td>浅白</td>\n",
       "      <td>硬挺</td>\n",
       "      <td>清脆</td>\n",
       "      <td>模糊</td>\n",
       "      <td>平坦</td>\n",
       "      <td>N</td>\n",
       "      <td>1.0</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>12</td>\n",
       "      <td>浅白</td>\n",
       "      <td>蜷缩</td>\n",
       "      <td>N</td>\n",
       "      <td>模糊</td>\n",
       "      <td>平坦</td>\n",
       "      <td>软粘</td>\n",
       "      <td>1.0</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>13</td>\n",
       "      <td>N</td>\n",
       "      <td>稍蜷</td>\n",
       "      <td>浊响</td>\n",
       "      <td>稍糊</td>\n",
       "      <td>凹陷</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>1.0</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>14</td>\n",
       "      <td>浅白</td>\n",
       "      <td>稍蜷</td>\n",
       "      <td>沉闷</td>\n",
       "      <td>稍糊</td>\n",
       "      <td>凹陷</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>1.0</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>14</th>\n",
       "      <td>15</td>\n",
       "      <td>乌黑</td>\n",
       "      <td>稍蜷</td>\n",
       "      <td>浊响</td>\n",
       "      <td>清晰</td>\n",
       "      <td>N</td>\n",
       "      <td>软粘</td>\n",
       "      <td>1.0</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>15</th>\n",
       "      <td>16</td>\n",
       "      <td>浅白</td>\n",
       "      <td>蜷缩</td>\n",
       "      <td>浊响</td>\n",
       "      <td>模糊</td>\n",
       "      <td>平坦</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>1.0</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>16</th>\n",
       "      <td>17</td>\n",
       "      <td>青绿</td>\n",
       "      <td>N</td>\n",
       "      <td>沉闷</td>\n",
       "      <td>稍糊</td>\n",
       "      <td>稍凹</td>\n",
       "      <td>硬滑</td>\n",
       "      <td>1.0</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    编号  色泽  根蒂  敲声  纹理  脐部  触感   权重 好瓜\n",
       "0    1   N  蜷缩  浊响  清晰  凹陷  硬滑  1.0  是\n",
       "1    2  乌黑  蜷缩  沉闷  清晰  凹陷   N  1.0  是\n",
       "2    3  乌黑  蜷缩   N  清晰  凹陷  硬滑  1.0  是\n",
       "3    4  青绿  蜷缩  沉闷  清晰  凹陷  硬滑  1.0  是\n",
       "4    5   N  蜷缩  浊响  清晰  凹陷  硬滑  1.0  是\n",
       "5    6  青绿  稍蜷  浊响  清晰   N  软粘  1.0  是\n",
       "6    7  乌黑  稍蜷  浊响  稍糊  稍凹  软粘  1.0  是\n",
       "7    8  乌黑  稍蜷  浊响   N  稍凹  硬滑  1.0  是\n",
       "8    9  乌黑   N  沉闷  稍糊  稍凹  硬滑  1.0  否\n",
       "9   10  青绿  硬挺  清脆   N  平坦  软粘  1.0  否\n",
       "10  11  浅白  硬挺  清脆  模糊  平坦   N  1.0  否\n",
       "11  12  浅白  蜷缩   N  模糊  平坦  软粘  1.0  否\n",
       "12  13   N  稍蜷  浊响  稍糊  凹陷  硬滑  1.0  否\n",
       "13  14  浅白  稍蜷  沉闷  稍糊  凹陷  硬滑  1.0  否\n",
       "14  15  乌黑  稍蜷  浊响  清晰   N  软粘  1.0  否\n",
       "15  16  浅白  蜷缩  浊响  模糊  平坦  硬滑  1.0  否\n",
       "16  17  青绿   N  沉闷  稍糊  稍凹  硬滑  1.0  否"
      ]
     },
     "execution_count": 92,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df_tmp=df_data.iloc[:,:-1]\n",
    "df_tmp['权重']=1.0\n",
    "df_tmp['好瓜']=df_data['好瓜']\n",
    "df_tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "id": "53adf2cd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CART分类树：\n",
      " {'纹理': {'清晰': '是', '否': {'色泽': {'乌黑': '是', '否': {'脐部': {'凹陷': '是', '否': {'根蒂': {'蜷缩': '是', '否': {'敲声': {'浊响': '是', '否': {'触感': {'硬滑': '是', '否': '否'}}}}}}}}}}}}\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAV0AAADoCAYAAABM+DfFAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8QVMy6AAAACXBIWXMAAAsTAAALEwEAmpwYAABLYUlEQVR4nO3deVhVVfvw8S8zivMsCqgpg6gIyiAKKeCYE6CYOEFOqWk4VT5amplDmTlnOJClOZA45hQiChIIgoIYgiOIAwqiiHI4nLPfP3w7v+c8YDkAB3B9rovrir332ftepjeLtde6l5YkSRKCIAhCudDWdACCIAhvE5F0BY0yMzNDS0ur3L/MzMw03XThLaUlhhcETdLS0uL27dvl/lxjY2PEX31BE0RPVxAEoRyJpCsIglCORNIVBEEoRyLpCoIglCORdIUKKTMzk48++kj1/aNHj5g1a5bq+5MnT/Lzzz/z888/c+LECbp164aPjw9WVlb4+PhgbW2NXC7XROiC8I9E0hUqpH379tGjRw8ACgoKqFWrFmZmZigUCgoLC6lWrRrXr1/nr7/+okaNGhgbG7N7927atm3L7t27sba2Rk9PT8OtEITidDUdgPB2+qfpWg8fPuT06dNs2LCBgIAAoqKiqFOnDg0aNGDjxo20atWK5cuX06lTJ/Lz83F0dOT+/ft4e3uTnJyMt7c3ly5dKsfWCMLLE0lXKDd37tzhxIkTnDhxgtDQULXhg/+2du1aCgoKGD16NP7+/jg6OqJUKhkxYgQDBw5k586dJCUlER4eTmFhIVZWVjRs2JDdu3fj7e3Nnj178PHxQZIktLS0yrmVgvDPxPCCUGby8vI4dOgQAQEBtGvXjrZt2xISEoK9vT0nTpzgk08+KfFzs2fP5uuvv8bc3BwvLy8sLS1JTU1FoVAgSRKGhoY0a9aMVq1aYWZmRuPGjbl9+zY+Pj5cunQJHx8fkpOTxZiuUCGJnq5QauRyOTExMYSGhhIaGsr58+dxcHDAw8ODLVu2YGdnh67uv/+Vu3XrFqNHj6ZLly7MnTuXL7/8kk8//ZQ//viDLl26AM9XlJmampKfn0/jxo2JjIwEwNvbm927d5dpOwXhTYhlwMJrkySJ5ORkVZKNiIjgnXfewcPDAw8PD7p160b16tX/8R4lLQPOy8sjISGBjh07UqNGDbS1tVm/fj3r1q3j2LFjNG/eHIBDhw6RlJSEmZkZ+/fvR5IkkpKSaN++PYWFhaxZswYTE5MSnyuWAQuaIpKu8EoyMjJUY7KhoaEYGRmpkmyPHj1o0KDBK92vpKQbFhbG1q1bkSSJBg0aMGXKFKZPn46uri4dO3Zk1qxZnD59mvXr12Nra8vw4cOxtLQEUI3p/huRdAVNEUm3gtu8eTO+vr5kZWUhk8k4deoU58+fZ/r06SgUCiwsLNSu/+CDD1i9ejXVqlXj2rVrHDlyBDc3N9q1a/daz8/NzSU8PFyVZB88eIC7uzseHh64u7vTqlWrN2pfSUn3/v37FBQUYGJiwtdff83p06f56quvcHBwYMuWLWzZsoWPPvqI/v37U6NGDXbv3s1vv/0GoOrpAvTt2xd/f3+1e/v7+5Ofn09kZCQ9evSgqKgIfX19JElCJpOphikEoayIpFvB/f777+zcuRNvb29u375NWloaV69eZcCAAUiSxL1799i3bx8ZGRmkp6czduxYNm3axLJly0hISMDZ2Rl3d3c6d+78Us+TyWRERUWperPJyck4OzurerM2NjZoa5fe+9d/qzKWlZVF/fr10dHRUR0rLCxET09PNTNBoVCgra2tNlNBkiSUSqXa5/6bsbEx3bp1w9fXl0mTJpVSawTh34kXaRXY48ePcXNz47333uPAgQMcOnSI7OxsHj58iEKhwNTUlJYtW/Ljjz+yfPlyIiMjuXjxIj/++CNGRkaMGTMGZ2dn9PX1X/gMpVLJhQsXVD3ZqKgo2rZti4eHB0uWLKFLly4YGhqWY6vVNWrUqNix/21PSYlVS0vrhQk3MTERgPT0dKysrHBzc2PQoEF8+OGHGBgYlELUgvBioqdbgSUmJvLJJ58we/Zsjhw5goGBATk5OTx69IhWrVpRUFBA7dq1VT3drKwsGjduzM2bN9mwYQMZGRmqX8379Omjuu/169dVSTYsLIz69eurhgu6d+9O3bp1y62N5VlPNy0tjbVr13Lp0iWSk5MZO3YsI0eOxNzcnHnz5nH69GmCgoJwcXEpl3iEt5Po6VZgHTp04NChQ0iSRKNGjZg6darq3O3btxkyZAgFBQWqnu65c+d4+PAh/v7+2Nra4u3tTWZmJvb29gQHB6sSbX5+Ph4eHvTt25fly5e/8A1/ZXb9+nUuX76s9sNGkiRcXFz4/vvvVTMg4PlQw5YtW4iIiKBJkyaaCFd4i4ikW8Hp6uqyZs0anJycaNy4serFUGJiIhkZGTRs2FB17bp163B1dWXgwIFs376d1NRUjh8/TqtWrXBxccHDw4OpU6dibW1d5Vdq6ejoMHPmTKytrVU/VMzNzalbty5WVlYApKSkMG/ePACSk5M5f/682MZHKHMi6VZwf/zxB7m5uWhpafH06VMePHgAPK+6paWlhSRJTJw4kevXr9O3b18uXrzI+PHj0dfXZ/Lkydja2nLkyJF/HNfVJFNTU4yNjcvs/o6Oji987n/PVOjTp88Lx4AFoTSJpFuBFRUVsWzZMkJCQkhNTeXChQvk5eUBcO/ePUxNTbl16xYZGRno6uqqenErV67k888/Z9GiRXh7e1fYhAtw8+bNMrt3YWEhdnZ2fPHFF/j4+ADPp8CZmprStGlTnJycVNempKSUWRyC8N9E0q3AkpKSGDhwILVq1eL27dt07NiRhg0bEhoaSnZ2Ng0bNsTHxwcvLy/V3NRhw4Zx9OhRxo0bB8CTJ0802QSN0tfXJzAwkKFDh9KrVy/q1KmDXC7Hzs6O8PBwtWv79OmDQqHQTKDCW0XMXqignjx5wunTp1UvvzIyMujevbtqvqy5uXmJ47IFBQUaneJVEU2aNAlJktiwYQNKpZK8vDxq166t6bCEt5RIuhWEXC4nNjZWlWTj4+Oxt7dXJdlOnTq9VLEYobjc3Fysra3ZvXs3Xbt21XQ4wltOJF0NkSSJv/76S5VkT58+TcuWLXF3d6dnz55069YNIyMjTYdZZQQHB7NgwQISEhIq9Bi3UPWJpFuOMjMz1YrFGBgY0LNnT9zd3XFzc1Ob/iWULkmSGDBggKpcpCBoiki6ZejRo0eEh4erEm1WVhZubm6qIYM3LRYjvJqbN2/SqVMn/vzzT3R0dLh8+TJ9+/bVdFjCW0Yk3VIkk8mIjo5W9WQvXrxIly5dVEm2Y8eOpVosRnh1K1as4Pfff2fq1Kls2rSJQ4cOaTok4S0j3sy8AaVSSVJSkirJnjlzBktLSzw8PPj6669xdnYWMwkqkNOnTzNgwAC2bdtGQkICd+7c0XRIwltIJN1XdPPmTVWSPXHiBHXq1MHDw4Px48ezfft26tWrp+kQhRe4du0aXl5eDB06lHXr1onZIIJGiOGFf5GTk8PJkydVifbx48eqilzu7u5irX4lc+PGDQICAjh58iR5eXnI5XKx/FcoVyLp/o+CggLOnDmjSrKXL19WFYvx8PCgXbt2Vb5YzNtg9+7dTJ48mYyMDKpVq6bpcIS3yFufdBUKBefPn1cl2ejoaDp06KBKso6OjmJepyAIpabMk65SqeSPP/7g1KlTxMTEEB8fryra8jd9fX06dOiAvb09zs7ODBo06F93kX1dkiRx9epVVZI9efIkTZo0USXZd999l1q1apXJs4XyZ2ZmRnp6erk/19TUtEyL+QiVV5km3RMnTjBp0iSqVaummjJlY2NTbGeCZ8+ekZycTEJCAlFRUSQmJvLFF18wZcqUUvlVPisri7CwMFWilcvlqiTr7u5epqUFBc0qz50p/pvYbVh4kTJLunFxcfTp04dVq1bRo0ePV0qeaWlpjBs3jpkzZzJx4sRXfnZ+fj4RERGqJHvjxg26d++u2sXW0tJSjMu+JUTSFSqaMku6/fr1w9XVlTFjxrzW55OTkxk1ahTXr19Xm+u6detWLl26xLJly1THioqKiIuLUyXZc+fO0alTJ1VvtnPnzmJ60FtKJF2hoimTpHv37l0sLS1JSEh4o8UBw4YNY8aMGQwePBhJkli0aBFbtmzh8OHDAKq5sqdOncLMzEyVZF1cXESxGAH496T75MkTatSoUeK5oqIidHV1VXV2X2VqmUi6wouUSfcvOjqazp07vzDhurq6FtsA8MqVK8THx6sdc3JyIioqiv79+zNmzBiioqJU5Q51dXXp2bMn77//PoGBgSVu1S0I/8bPz4+5c+dia2tb7NzIkSMZO3YstWrVYvz48bRu3RpDQ0NSUlKYO3cu3t7eGohYqOzKJOlGRUWV+Jf4bwYGBsW2ub57926x6+zs7Fi7di0jRoxg9+7dNG/eHD09PdavX0/fvn3FVC7hjWzevJm8vDyWLFmCJEmcP3+eP/74gxYtWgAQGBjI77//Ts+ePVm+fDlhYWF4enoSHBwsEq7w2sqk+kpqairm5ub/eI2rq6val56eXrFrLCwsSEtL45dffuHPP/9kzpw56OvrM3fuXCZNmlQWoQtvAUmS+PHHH4mPj+fIkSPs3r2bPn368Mknn6gS7p9//klgYCCDBg0CoFOnTly4cIGxY8fi7OzMrVu3ePbsmQZbIVRWZdLTlSTpH8e/zMzMWLhwodqxBg0aFLtOR0cHSZLQ19fHyclJbSNBQXhdqamppKSkEBYWxvvvv8+jR4949OgRpqambN68mcWLF9O1a1d+/vlnTp8+zaFDh0hISGDevHlYW1szb948pk2bxvLly3n//fc13RyhkinXV/ppaWls27YNExMTTExMip1fsGABvXr1wtnZuTzDEqqQgoICQkND2bt37wvnX1tYWLBkyRLS09PZvXs3UVFRREVFMWvWLJYvX46BgQEGBgasXLkSSZJ45513yM3NVQ1FzJo1izlz5tCyZctybp1QFZRr0jUzMyMgIICwsDAsLCzIysoiJiaGadOmoVAokMvlZbYSTai68vLyOHz4MCEhIRw7dgwbGxs8PT3x8fFh0aJFL/xccnKy2tist7c3GRkZ2NvbAxAWFkZqaipjxozh3LlzPHnyhLt375KSkoKVlZUo2ym8ljJJutra2sjl8mLH9fX1Vdtir1y5EkNDQw4ePEhiYiKSJOHr68vAgQNV18vlclH0WyjR/fv3OXDgAHv37uX06dN069YNLy8v1qxZ89IzWaytrdmzZ4/asZSUFNVOwfv372fq1KnMnTuXrKwsJEni5s2b7Nu3jx07drBkyRIsLS1LvW1C1VYmSdfa2pq//vpLLYH+7e+9wWbOnImLiwteXl7MmjWrxPtcunSJtm3blkWIQiWUnp7Ovn37CAkJISEhgd69ezNixAi2b9/+yluqa2lpIZPJih23tLTk8OHDKBQKLl68iLW1NevWrQPg9u3bfPPNN6xcubI0miO8pcok6To7O7N06dJix2/dusXChQvZuXMnWlpabNy4kTNnzhAWFkZBQQE5OTn4+fkREBAAwLlz58T4bgWVnZ1NzZo1y3zaXkpKCiEhIezdu5fr168zYMAAZs6ciYeHxxuVZDQwMEBPT4/BgwertUFLSwtDQ0Ps7e2ZP3++2mcKCwtLTNSC8CrKZEVadnY2rVq1IjY2lpo1axY7V79+/Ze6z4ABA/jqq6/E5oEV0Keffkrnzp0ZOnRosXMjRozg6tWrGBoacu/ePSRJUi2GkcvlnDlz5oX3lSSJc+fOsXfvXkJCQsjLy2Pw4MF4eXnh6ur6ysu5y3sZsL+/P/n5+URGRtKjRw+KiorQ19dHkiRkMhmRkZHlFotQMZVZ7YVhw4bxzjvvMHXq1Nf6fExMDDNmzCA1NVXUTahgOnXqhEwmo06dOujq6iKTyXB3d1e9tPrggw8YN24c0dHRNGrUiKKiIrKysvD09GTcuHGcOnVK7X4KhYLIyEj27t3L3r17MTAwwMvLC09PT+zt7d9oXF+TtRe6deuGr6+vmFMuqCmzbLZw4UK6detGvXr18PHxKXHxQ0kkSSIiIoIZM2awatUqkXArIB0dHS5evKj6/vDhwyQkJKi+VyqVNG3aVFVpTi6Xc/HiRWbNmqWqRyCTyThx4gQhISEcOHCA5s2b4+npyeHDh2nbtm2lrgKXmJgIPB+DtrKyws3NjUGDBvHhhx9iYGCg4egETSvTeroXLlxg+vTpXL58mXfffRcbGxs6duxYYj3dixcvkpCQwJ9//olCoWDJkiV4enqWVWjCG3ByciI6OhpJkpg2bRrx8fGsWrWKzp07A7Bo0SJCQ0MB1IYXFAoFRkZG1K1blyNHjtC+fXu8vLwYPHhwmc15LaueblFREdra2mq98LS0NNauXculS5dITk5m7NixjBw5EnNzc+bNm8fp06cJCgoqtgReeLuUy3Y9ycnJREREEBMTQ1xcHI8fP1Y7r6+vT8eOHbG3t6dLly507dpVTBWrwCwtLfnss8+A52P09erVU/VMhw0bxunTp7l8+TLa2tpERERw+/ZtHj9+zOXLl2nbti0ffvghgwYNonHjxmUea1kl3W3bthEXF6c2kyE1NZXExES8vLxo3ry5Kul2794dgIiICJo0aUKbNm1KPR6h8njr90gTXl10dDRFRUXFjvv7+3Pu3DkSExM5evQooaGhnD9/njZt2uDn54erqytGRka0aNGi3BbBaGq7HgMDA1XPH553PM6fPy92jxZE0hVe3vbt29m2bVuxuhoFBQUsWLAAHx8fdHR0uHv3Lo0aNaJx48bUr19f7XpJknB0dCxWe6MyOnToEDNmzCAxMVG1Oi0nJwcvLy/Cw8PVru3Tpw+bNm2iefPmGohUqEhE0hVeiyRJJCQksHfvXoKDg8nKyqJevXps2LCB77//nv379xMYGMiAAQOIi4tDJpMxePBgRowYUWwVWGXm7e1Nu3bt+PLLLwHIzc3F1NS02KKelJQULl68KJKuUDalHYWqSaFQEBERwfTp02nZsiU+Pj7IZDJcXV0ZNGgQYWFh6Ojo0LJlS3R1dUlPTycpKYkmTZoQGxuLoaEhurq6XLlyRdNNKTWrV69m/fr1pKSkAM/nIdvZ2REdHa325eTkpNqBQni7iZ6u8I9kMhlhYWHs3buX/fv307RpU9Uc2nbt2hWb2iWTyXj69Cl169bl2bNnGBgYqL0UVSgUr7TtTWWwevVqQkJCOHnyJJIkkZeX98rLkoW3h0i6QjFPnjzh6NGj7N27VzVv9u9E26pVK02HV+EoFAocHR356KOP8PPz03Q4QgUnkq4APH8BdPDgQVWPrUuXLnh6ejJo0CCaNm2q6fAqvPj4ePr27UtycnKJBfkF4W8i6b7FMjMz2bdvH3v37iU2NhZ3d3e8vLx47733ii1gEf7d9OnTyc3NJSgoiMLCQrS1tcWKSqEYkXTfMmlpaapiMqmpqfTv3x9PT0969+4tCsi/oby8PKytrfn5558JDQ2ladOmTJkyRdNhCRWM+DFcxUmSxIULF1SJ9sGDBwwePJiFCxfSvXt3saNyKapZsyZr1qxh4sSJjB49mps3b2o6JKECEkm3ClIqlfz555+qOrRaWlp4enry448/4uTkJJZYlxFnZ2d69OiBubk5586do0aNGpoOSaiARNKtIgoLCzl58iR79+5l3759NGrUCC8vL/bu3UuHDh0qddWuyuK3335jxowZXLhwgfv379OpUydNhyRUQGJMtxLLz8/n2LFjhISEcPjwYSwtLfH09MTT05PWrVtrOry31vHjxxkxYgRyuZzc3FxNhyNUMCLpVjIPHz7k0KFDhISEEBYWhoODA56engwePPiFW44L5S8/P5+TJ0/Sv39/TYciVDAi6b4ESZLIzMwkNjaWhISEYvtkGRkZ0alTJ+zt7V96J9pXcefOHdXUrujoaNzc3PDy8qJ///7Uq1ev1J8nvBxNVTAzNTUVL+kqMZF0/0Fubi7r1q1jw4YNPHv2DFtbW6ytrYtNrXr8+DFJSUmcP3+eJk2aMGXKFMaNG/dGU7CuXr2qmnHw119/8d577+Hp6UmfPn0wMjJ606YJpUCTWwGJf7aVl0i6L5CZmYmLiwudOnVi4sSJL7WFjFKpJC4ujrVr15KTk8PJkyepVauW2jUymQx9ff1i95IkiaSkJFWivXfvHoMGDcLLy4sePXqIqV0VkEi6wusQSfcFfHx8aNasGZ988skrf1aSJKZPn46JiQnLly9XHb969Sru7u7s27ePjh07olQqiYmJUU3tUigUeHp64uXlRZcuXapcYZiqRiRd4XWIpFuCGzdu0LlzZ/7888/Xnmt569Ytevfuzc2bN6lZsyaXL1/Gw8OD//znP7Ru3Vo1tatevXqqYjIdO3YUU7sqEZF0hdch5umW4MSJE3Tv3v2NJrc3b94cCwsLYmJiqFOnDr1798bCwoJ58+bRpk0bPD09CQ8Px9zcvBQjFyqyLVu24O/vr/aD9fHjx+jr66t2nhCqPpF0S/Dnn39iZ2f3wvOurq40adJE7diVK1eIj49XO2ZnZ0dUVBTr168nNzeXhw8fMnjwYDp37sygQYPEFK8qzN3dHSMjI5o1a8aaNWvQ1dUlMTGR9PR0mjVrhlKpRF9fn9OnT3P27FnV9kXbt29XzY7p3bs3zZo102QzhDIg1oOWIDY2Fltb2xeeNzAwwMXFRe2rpF5xx44dOXv2LJmZmaSlpfHdd9/Rtm1b4uPjSUpKKssmCBpmbGxMUFAQBgYGTJ48GSsrKzIyMhg+fDg9e/bkjz/+wNPTk19++YXExETc3d0JDg5m69attG7dmqCgIDFLpYoSPd0S5OfnF5t18L9cXV3Vvt+3b1+xa2rXrk1+fj46Ojq0atWKVq1a0a9fv9IMVaig/nsIITAwkJkzZ/Lhhx/y9ddfs2LFCurVq0deXh55eXkMHz4cT09PhgwZQnBwMDY2NpiamlKnTh3NNUAoMyLpvgYzM7Niu9mKwtXCf7t79y7+/v6qnTamT5/OkCFD8PLyol69ely5coW8vDx+++03rl27RqtWrTh+/DgAoaGh9OrVS5PhC2VIJN1XkJaWxrZt2zAxMcHExKTY+QULFtCrVy+cnZ01EJ1QngoLC//xfJ06dfjhhx+YM2cO33zzDUlJSUyePJno6Gj8/f0ZMGAAVlZWzJ8/X/WZv4cTbGxsmDFjBkOHDhU1jqsgkXRfgZmZGQEBAYSFhWFhYUFWVhYxMTFMmzYNhUKBXC4X/0iquLS0NDZt2sRPP/0EPF8QU1KpzPT0dMaPH4+pqSnDhw8nIiICT09Prl69yvDhw2nRogUrV64kNjYWHR0dcnJy+P333wFo3bo1np6eBAUFiSLoVZB4kVaC+vXrc+/evWLH9fX1qVu3LoGBgejo6GBoaMjBgwcZN24cEyZM4MyZM1SrVk11/b1792jYsGF5hi6UAZlMxq5du3B3d6dbt25IkkRERARAiQk3Pz+f9u3bs3HjRgBMTEwwNDSkZs2aaGtrq/7uPHjwgKVLl7J7927q1auHnp4eAImJiaSkpJCXl1d+jRTKjejplsDJyYlz587RpUuXYudCQ0MxMDBg5syZuLi44OXlxaxZs0q8z4vuIWjeo0ePqF69uirRlSQ1NZWNGzeydetWOnTowMSJExk0aBAGBgb/eO/IyEjatGnDX3/9hba2NnFxcSVO/dLW1mbGjBlUq1aN5ORkJElCkiTu3buHubk5vr6+b9xOoeIRSbcEzs7Oql8f/9utW7dYuHAhO3fuREtLi40bN3LmzBnCwsIoKCggJycHPz8/AgICgOc7xH744YflG7xQTEpKCnFxcQDUqlWLgQMHMnv2bDw8PPDx8VG7tqCggJCQEAIDA0lJScHPz4+oqKhXqk9879493n33Xc6dO4e/vz+zZs1i1apVABQVFaFUKoHnUw9Xr15Ny5YtGTduHHK5HJlMRs+ePV94b39/fwA8PDxQKpUUFRWhr6+PJEnIZDIiIyNf6c9GKH9iGXAJsrOzad26NWFhYcUWQWRnZ1O/fv1/vUdSUhJ+fn7cuHFDFKspQ/Xq1aNDhw6kpaVx5swZbty4gZ+fHy1atCAjI4OrV6+yfv160tLS0NXVpaCggAULFmBnZ0fLli3Jy8tTDR9s3ryZX375BVtbWyZMmMDAgQP/8f/dyy4DLigoKNUVZ8bGxuTl5dG3b198fX2ZNGlSqd1bKHtiTLcE9evXx8/PjwULFlBUVFTs3L95+vQpCxYsYNasWSLhljFbW1vCw8Px9PRUHfPz8yM8PJyWLVsCUL16dWxsbHj06BEjR45kypQprFu3jiNHjtC8eXOUSiUeHh4YGhoSExPD8ePHGTJkSKn9vyuLJb5OTk6kp6djZWWFm5sbq1atKlbnWaiYRNJ9gcWLFyOTyejVqxfbt28nIyPjH4uMKJVKrly5wsaNG3Fzc6NNmzZ8/PHH5Rjx2+lVCgTFx8dja2uLq6srISEhNG/enLt37/LVV1+Rnp7O4sWLVfNqK6K0tDTV36kff/xRNQyxbds2Lly4gLW1teoFn1BxiTHdF6hWrRpHjhzhxIkT/PDDD3z33XfI5XI6dOhQbHnmo0ePuHDhAnXr1qVbt27s3r0bR0dHDUX+djIwMMDX1xeZTIa3t3ex8zKZjJo1a9KpUydSU1MxNjZm7dq1HD9+nK+++orz58/z1VdfaSDykp08eRJJknBzc1MdkyQJFxcXgoOD6dq1K0FBQcDz4YYtW7YQERFRbDhMqHhE0v0HWlpaeHh44OHhATwvbJ6QkEBBQYHadTVq1MDOzq5MtuoRXs53331X4vGkpCS2bdtGdHQ07dq145133sHU1JQPPvgABwcHmjVrRrt27Src9Ky6devi5+dHWFiYaksmc3Nz6tatC0C3bt0AmDdvHgDJycmcP38eMzMzzQQsvDSRdF9Bs2bNRNWnSiA/P5/du3cTGxtL37596dSpEzNnziQtLY2xY8fy/fffU69ePQwNDalTpw61atV6raRrampa5pXi2rVrV+yYgYFBsVkKffr0EUXvKwkxe0Go1Jo2bYqFhQUAT5484c6dO2RlZVG7dm2qVavG9evX2bp1Kzo6Ovj5+QHQv39/8vLyVHN0Hz58yIABA1iwYIGGWlGyx48fY21tzS+//EL37t2B5/v2mZqa0rZtW7VrU1JSuHjxIs2bN9dApMKrED1doVIzNzdn1KhRBAYGkpWVxcSJE/nggw9o3rw5Li4u6OrqUlRUpDaDoKCggD179qiKFIWHh/PHH39oqgkvVKtWLdauXcvEiRO5cOEChoaGyOVy7OzsCA8PV7u2T58+KBQKzQQqvBLR0xUqpfj4eDZu3MiuXbtwdXVlwoQJ9O7du0r+iu3l5UX79u358ssvUSqV5OXlUbt2bU2HJbwmkXSFSiMvL4+dO3fy448/8uDBA8aNG4e/v3+VH2fPzMykY8eOnD59GisrK02HI7whkXSFCk2SJM6dO0dgYCDBwcH06NGDCRMm0LNnzyrZq32RtWvXsmvXLk6dOlVikR2h8hD/94QK6fHjx2zYsIFOnTrh4+NDy5YtuXTpEiEhIW/lm/pJkyYhl8vZvHmzpkMR3pDo6QoVhiRJxMbGEhgYyJ49e/Dw8GDChAm4u7uL3h3PSz56eHiQmJjI5cuXUSgUaosnhMpBJF1B4x49esT27dsJDAzkyZMnjB8/Hj8/Pxo3bqzp0Cqczz77jJs3b+Lo6Mi1a9dYvXq1pkMSXpGYMiZohCRJREdHExgYyN69e+nduzffffcdPXr0EL3aF/jll18YNWoUAwcOxMzMjDt37mg6JOE1iKQrlKuHDx+ybds2AgMDKSgoYMKECSxbtkwsoX4JeXl5uLq60r9/f3766SdVFTWhchHDC0KZkySJqKgoAgMD2b9/P/369WPChAm8++67r1QlTICbN28SEBDAkSNHMDQ0JDc3V9MhCa9IJF2hzOTk5PDzzz8TGBiIUqlkwoQJjB49WmxXXwp+/fVXli5dSmJioqZDEV6RSLpvEUmSyM3NLbZctEaNGqVWaPvvTRsDAwM5dOgQ/fv3Z8KECbi4uIherSAgkm6Vd/PmTVVpw7i4OPLz84ttxvjs2TMsLCxwcHDAw8MDT09PdHVfbbj/wYMHql6ttrY2EyZMYNSoUS+104ZQMjMzM9LT08v9uaampty8ebPcn/u2EEm3iiosLGTq1KkEBwczePBgHB0dsbW1pXnz5sV6nM+ePVPVYz1y5AiZmZls2bIFd3d3tesSExOJi4vjgw8+AJ73ak+dOkVgYCCHDx9m4MCBTJgwga5du4pebSl42T3YSpuxsfE/7pIivBmRdKuoKVOmkJqaytq1a6lVq9Yrffb06dNMmTKFyMhILC0tAbhx4wbdunVj9erVuLi4sHXrVgIDA9HX12fixImMHDlSVWBbKB0i6VZNIulWQRkZGdjY2HDmzBnq1KnzWvdYvXo1mZmZ/Pzzz2RnZ9O1a1c8PDy4f/8+x44dw9PTkwkTJuDk5CR6tWVEJN2qSSTdKujbb7/l4sWLLF269LXvkZubi729Penp6dja2nL//n1MTEwYP348Y8eOFb3aciCSbtUkFkdUQVFRUaqdYv+Xq6trsc0Lr1y5Qnx8vNqxOnXq0KpVK0JDQ9HX16d169Y8ffqUhQsXsnDhQi5fvkzTpk3LrA3Cv+vbty9Hjhxh+/btbNy4kUaNGiGTyTA3N+fLL78kLS0NLS0tAgICVMuFJ0+ezPr16ykqKsLc3Jzq1atruBVvH5F0q5i/l9fOmTOnxPMGBga4uLioHbt7926J19ra2nL79m3S0tLUjhcVFb3y7Aah9OTk5Kj+n0RHR6Orq4uzszPOzs5kZ2dz+fJlCgsL+euvv9DT00MulxMREYGOjg5FRUWq86ampiLpaoD4l1PFFBYWkp2d/Y97Zbm6uqp9v2/fvhKva9WqFdeuXSt2XCRczXr8+DFnzpzhxo0bnD9/nnr16lGrVi0aNmwIPP/BW1BQQEhICADZ2dls374dSZIwNDRk165dwPNNL//eaVgoP+JfTxWkpaX1wpdbZmZmLFy4UO3Yi1aIicIzFVOLFi2wsLCgevXqKJVKdHR0+P3334mNjUUmk2FlZUXjxo359ddfUSqVjBs3jq1btyKTyRg9ejS7du1CqVSKF6AaIpLuWyItLY1t27ZhYmKCiYlJsfMLFiygV69eODs7ayA64VX9/vvv1K5dm/j4eBo1asRHH33E8ePH2bhxIytXruTEiRMEBgYCkJ6ezrBhw8jPzyczM5Nhw4YBMHz4cDw9PTXZjLeSSLpvCTMzMwICAggLC8PCwoKsrCxiYmKYNm0aCoUCuVwuxvcqiaSkJB49ekSDBg2YNm0ahw4dAp6vJPPz86NLly48fvyYoUOHMnToUAD27NlDUVGRKuHGx8dz8eJFjbXhbSZ+f6xitLW1kSSJoqIiteP6+vrUrVuXwMBAdHR0MDQ05ODBg4wbN44JEyZw5swZqlWrpvaZgoICMX6rYbdu3Sp2LCkpiRkzZgDQoUMHLCwsAPD29iY3N5cPP/wQLy8vunbtio2NDT4+Pqxdu5YffvgBHx8f7OzsqFOnDqNHjy7XtgjPiX9RVYyenh5t2rTh0qVLdOjQQe1caGgoBgYGzJw5ExcXF7y8vJg1a9YL75WcnIyXl1dZhyz8j4KCAn744QcADh48yKRJk9TO+/r6AqgKFz1+/JjQ0FDu3r1L9+7d8fPzY8GCBdSsWZMuXbqwYcMGVU93yJAhTJkyBX19/fJtlKAierpVkJOTU7F5t7du3WLhwoVs2LCBzZs3I5fLCQ8Pp1+/fri5udGxY0dWrlyp9pn4+HicnJzKMfK3l1wup6ioiKCgICwsLAgPDwcolnD/W15eHvB8yp+NjQ2TJ09mxowZ9OrVC21tbbS0tFRbtstkMgoLC4mKiqJhw4ZijrUGiRVpVdDWrVvZvn07W7duVTuenZ390lW/0tLSGDp0KHfv3hVvuV/RwIEDOXDgAM+ePWPFihXk5eXh7u5OXFwcc+bMITk5mW3btrFkyRLg+RSvVq1aYWBgQOPGjVm6dCldunTRyIo0f39/jh07hru7O0qlkqKiIvT19ZEkCZlMRmRkZLnGUxWJnm4VNHToUC5cuEBycrLa8Vcps7hmzRqmTJkiEu4riIyMpHv37kRHR9O9e3fVD7m4uDhu3LhBgwYNePr0KVu3bmXy5MlER0djbGxMnTp1ePDgAdWqVaOwsJA9e/ZorA1BQUHA87nbcrmc4cOHExoayokTJ0TCLSUi6VZB1atX55tvvsHPz49jx46hVCpf+rP379/n888/JzExkY8//rgMo6x68vLy8PPzw83NjRo1aqCtrY22tjZ5eXloaWmhUCi4evUqenp6bNiwgfHjx5Ofn0/v3r1JTEzk4MGDrF+/nm7dumm6KTg5OZGeno6VlRVubm6sWrUKmUym6bCqBPEirYoaM2YM9evX54svvmD+/Pk4ODhgY2ND27Zti71EycrK4vz581y4cIHExESGDRtGZGQktWvX1lD0ldP//lawceNGIiIiuHbtGjt37kSSJK5cucK+fftIT09n+fLl/PbbbyxZsoTw8HDWrFlDQEBAucyVzs7OpmbNmmp/F9LS0li7di0AP/74o6rXu23bNubNm4e1tTVBQUHFlpELr0aM6VZxkiSRnJxMTEwMZ8+eJSkpqdh0svr16+Pg4ICjoyNdunQRFcRe0+HDh1mxYgXp6enI5XIuXbrE8uXL6dGjBykpKfz6668kJibi4ODA7NmzCQ4O5siRI1y7do1u3bpx7do1LCws2LFjB02bNi3TMd3ly5eTlZXFN998ozqWmppKYmIi06ZNQ5Ikxo0bx8iRI+nevTsAERERNGnShDZt2pRJTG8NSRCEUhERESEdOXJEGjZsmJSRkSFt3rxZaty4sdS4cWNJW1tbsrS0lNavXy+1bt1amjp1qnTmzBmpd+/ekiRJkpeXlyRJkvTxxx9LGRkZkiRJkqmpqQSU+5eWlpbUtWtXta86depIN27c0NifbVUihhcEoZT8PRb7008/MX36dAwMDHj8+DEeHh5kZ2eze/duioqKcHBwoG3btmqLUf788088PDxITU1VzZ0u633KfvvtN+bPn09CQoJqmCEnJwcvLy/VlLW/9enTBx0dnTKN520hkq4glJKdO3fy888/c+XKFW7cuEGPHj3w8/Nj3LhxGBkZce3aNZRKJQkJCQQGBvLuu++qPuvs7Mxvv/1GQEBAucXr7e3N1q1b+eabb5g3bx7wfEVjSfOzU1JSyi2uqk4kXUEoBUqlknv37nHp0iWsrKzYvn079vb2/Pzzz/j7+9OwYUMyMjIYOXIkcrmcYcOG4eDgwObNm1UbfHbv3p0rV66U26wRLS0t1q1bh52dHT4+PpibmyOXy7Gzsyuxp/v3CjjhzYgXaYLwBiRJ4vDhw/znP/+hevXqLFmyRPXiqbL4/vvvOXjwICdOnECSJPLy8sTMlTIkkq4gvKbIyEjmzJlDTk4OixcvZuDAgZVyMUlRURGOjo5MmzaNMWPGaDqcKk8kXUF4RYmJicydO5ekpCQWLFjAqFGjKv1Lpvj4ePr27UtycvILi9oLpUOsSBOEl3Tt2jVGjhxJr1698PDw4PLly/j5+VX6hAtgZ2fHiBEjmDlzJgAPHz6koKBAw1FVTaKnKwj/4u7duyxatIgdO3bw8ccfM336dGrWrKnpsErdkydPsLa2ZsuWLRw4cABra2smTJig6bCqHNHTFYQXePTokWr5q76+PikpKXzxxRdVMuECGBoasm7dOiZOnEjNmjXJyMjQdEhVkki6gvA/nj17xvLly2nTpg23b98mISGBFStWqHbbrapsbW05evQo1tbWxMfHc+fOHU2HVCWJpCsI/19RUREbN26kTZs2REVFER4ezpYtWzA1NdV0aOUiPDwcuVxOdHQ0YWFhpKamajqkKkmM6QpvPaVSyZ49e5g3bx7GxsYsXboUR0dHTYelMWfPnmXIkCE8efKEnJwcTYdT5YikK7y1JEkiNDSUOXPmIEkSS5YsoWfPnpVyrm1pKyoqIiUlhXbt2mk6lCpHLAMWKrycnBzi4uKIiYkhLS2N/+0nNG/eHAcHBxwcHGjWrFmJ98jIyGDdunUsXboUeN6bmzNnDhkZGSxatIghQ4agrf12jbaZmZmRnp5e7s81NTUt82I+FZno6QoV1smTJ1m8eDHR0dF06NCBjh078s4776jNi5UkiVu3bnHhwgUSEhJo1qwZs2fPZsSIEaoeq0KhwN3dnV69euHp6cncuXM5e/Ys8+fPx8/PDz09PU01UaM0sQcbgLGxcbEfnG8T0dMVKqQNGzawaNEiZs+ezaZNm15qy3BJkggPD2fZsmWcOnWKwMBAtLS0+Pbbb5HJZKSmpuLq6sonn3zC9u3b1UorCkJ5ET1docK5d+8elpaWHD58mBYtWrzy5/Pz8+nVqxdBQUHI5XL69euHgYEBw4YNw9fXFwsLixcOQ7xNRE9XM0RPV6hwNmzYwMCBA18r4QIYGRkxefJkvvvuO549e0a1atVo1KgRsbGxXLhwgffee48FCxaUasyC8LJE0hUqnJMnTzJx4sQ3ukfv3r1ZtGgROTk5b90LMqFiE0lXqFCKioo4d+4cHTt2LPG8q6srTZo0UTt25coV4uPj1Y41aNCAevXq8ddff2FtbV1W4VZJ169fJz09nTNnzqClpYWzszNt2rTh7Nmz5OfnM2LECBQKBd7e3lSrVg0tLS0ePnxITk4O77zzDvB8Vd+iRYvEn30JRNIVKpTU1FQaN25MnTp1SjxvYGBQbAvwu3fvlnitjY0N586dE//wX5Genh6SJGFvbw88Xzyiq6uLrq4uGzZsYOfOnSxatIidO3dSWFiIjo4OMTExREREMGvWLJRKJUCVrVHxpkTSFSqUgoICjIyM/vEaV1dXte/37dtX4nU1atQQ5QlfQ/Pmzfn8889xcHBAW1ubqKgotm7dCsBHH33EsGHDAIiJiWHfvn1qi0m+/vprJEnCwsICPz8/TYRf4YmkK1QqZmZmLFy4UO2YKLpd+qysrDh79iwAbdu2ZcmSJRw9ehRdXV3OnTvHN998Q/Xq1V9Yn8Hc3Lw8w61URNIVKoW0tDS2bduGiYkJJiYmxc4vWLCAXr164ezsrIHoqpZz585x584dLC0tAUhPT8fFxYXhw4fj7e3N119/DTyfmmdiYsLKlSuJiori5MmTzJ07V/XfQslE0hUqnJLmcJqZmREQEEBYWBgWFhZkZWURExPDtGnTUCgUyOVyqlev/q/3Ef5dfn4+LVu25NSpUwB06tSJVq1asWnTJlq2bKmqx/Do0aMX3kP82b+YSLpChdKkSRMyMzORJEltrFBfXx99fX0CAwNZuXIlhoaGHDx4kMTERCRJwtfXl4EDB6rdKzMzk6ZNm5Z3E6qEwsJCLCwskMlkSJJE9erV0dbWZsWKFWzevBmACxcucO7cOXx8fFSf8/HxwcDAAE9PT02FXuGJpCtUKMbGxhgZGXH9+nVatWqldi40NBQDAwNmzpyJi4sLXl5ezJo1q8T7KJVK4uPjcXJyKo+wqxx9fX0uX74MQP369YHn47Tx8fEYGRmRmZnJr7/+yu7du8X47SsSSVeocJycnIiNjVVLurdu3WLhwoXs3LkTLS0tNm7cyJkzZwgLC6OgoICcnBz8/PwICAgA4PLlyzRo0KDK7/ZQGs6fP0/btm1V9S3u3buHgYEBe/bs4eHDh0yePBmFQqGqYzF69Gh69erFp59++soJ19/fHwAPDw+USiVFRUXo6+sjSRIymYzIyMhSb19FI2ovCBVOcHAw3377bbHpSNnZ2ape17+ZO3cuDRs2ZNmyZWUVZqWwY8cOvLy8MDAwAGD//v3ExMSwePFitLS0mDJlCnv27OGXX37hnXfewdDQkICAAIYPH65WyF0ul6uqsRUVFSFJ0mtXZzM2NiYvL4++ffvi6+vLpEmT3ryhlYhYHylUOF5eXjx58oSgoCC14y+bcM+cOcOBAweYPn16WYRXaSiVSq5evarqVcLzhQ96eno8fPgQgMjISBo2bMhXX31FcHAwPXv2JCYmhqVLl+Lt7U3Pnj1JS0tTS7C6urpvXA7TycmJ9PR0rKyscHNzY9WqVchksje6Z2UherpChXTlyhX69+9PrVq1GDFiBJ06daJly5Yl1lGQJIk7d+5w/vx59uzZQ1xcHDt37sTNzU0DkVc8jx8/ZvXq1ezYsQMdHR2ys7PJycmhoKCAEydO8Pvvv2NiYoIkSURHR7Ny5UrVZwMCApgyZQpt2rR54zjS0tJYu3YtwcHBREZGEhQUxMiRIzE3N2fevHmcPn2aoKCgYisOqxoxpitUSK1btyY5OZmQkBB27drFihUryM3NpU2bNsWKmGdkZCCXy3FwcKBfv34EBwf/66q2t8Hx48fZs2cPc+fORV9fny+//JL4+HhWrlzJqlWrmDhxIrq6/5cC/u69fv7551y6dAkLC4vXfvYPP/yAk5MTtra2qmOSJOHi4kJwcDBdu3ZV/SZjbGzMli1biIiIKFZXoyoSPV2h0sjKyuLKlSvF5oAaGxvTokULsbdZCWJiYtQK2ERHRzN48GCWLVtGkyZNNPIr/d9FdP5bcnIy58+fx8zMrNzjKW8i6QpCFZabm8utW7fw9PTk7t27tGjRgvz8fExNTSkqKmLTpk2sXLkSY2NjWrZsyYkTJwBYtGgRn332Gbq6unz22Weq1WkvS5Ik+vfvT9euXfnPf/6jOp6Tk4OXlxfh4eFq1/fp04dNmzbRvHnzN25zRSeGFwShClu6dCmBgYG4u7vz6aef8uDBA6Kjo/nss88ICQmhqKiIa9eukZubq9pNw9LSkpEjR6peor0OLS0t1q1bR+fOnfHx8aF169YAaGtrlzh/OiUl5c0aWplIgiBUSb/88oukq6srbdmyRXXsyJEj0vz586Vnz55Jbdu2ldLT06UjR45IMplMunr1qjRmzBjVtXK5XBoyZIiUkpLy2jF8++23koeHh6RUKiVJkqSsrCzp3XffLXZd7969pRs3brz2cyoTMbwgCFVMUVERs2fPZseOHVhZWXHkyBE8PDzQ1tamWrVqVKtWjfr165ORkcGgQYOYMmUK8HzGyKJFi/jpp58AmDdvHrGxsezfvx9DQ8PXjsXe3p6ZM2cycuRIlEoleXl51K5du7SaW+mIpCsIVUhWVhbDhg3D0NCQ7du3U1RURKNGjdQWN/zt4cOHFBQUlHl9itjYWAYOHMjFixdfeq51VSaSriBUEXFxcXh7ezNy5EgWLlyoNrVO0z7++GOePHmiKpbzNhNJVxCqgJ9++onZs2fz448/4uXlpelwisnLy6Nt27Zs27aNd999V9PhaJRYBiwIlZhcLmfq1KksXryYU6dOVciEC8/3S1uzZg0TJ05EJpOxfPnyt2vGwn8RSVcQKqm7d+/i7u7OjRs3OHv2LG3bttV0SP9o8ODBWFlZsWTJEuLj44mNjdV0SBohkq4gVEIxMTHY29vj5ubG/v37X7h7ckUhl8v57LPPmDNnDmvXrsXAwOCFuzhXdWJxhCBUMps2beI///kPmzZtKrZbRkWlq6uLkZER/fr1o2vXroSHh1f4HxRlRfR0BaECkySJTz75hGfPniGTyfjwww/57rvviIiIqDQJF56vUPv888+Jjo6moKCA9PR0oqKiNB2WRoikKwgV2MmTJzl48CDZ2dn06NGDe/fuERMT80YVwDSpdevWHD16lO+++4727dtrOhyNEFPGBKGc5OTkkJmZWex4y5YtqVGjRomf6d27N3Z2dvz8889MnjyZOXPmlFhTWKg8RNIVhDIil8v57bffOHDgALGxsWRlZdGsWTO1EpQKhYJbt27RsmVL7O3t8fHxoU+fPmhpaREfH4+bmxt6enpMnz4dLS0tOnXqRK9evTTYqpdnZmZGenp6uT/X1NSUmzdvlvtzX5ZIuoJQBs6dO4e3tzfNmzfHy8sLOzs7WrduXeIqscLCQlJSUlQ7Xujo6LBv3z68vLw4f/481atXx87ODgcHB0aPHk2HDh000KJXp6Wlxe3bt8v9ucbGxsVqLlckIukKQinLzc3F0tKSr7/+mn79+r3SZyVJ4scff+S3335jyZIlNGrUiM6dO6vt8FBZiKRbMjE4JAilbO3atbi6ur5ywoXniWrixIkYGRlRUFCAk5NTpUy4wouJpCsIpWzXrl2MGjXqtT+vpaXFqFGj2LlzZylGVfnl5uYil8tVOxlXVuJHqCCUory8PK5du/bCcVdXV9dimy9euXKF+Ph4tWP29vYsXrwYSZKq5N5v9+7d47PPPmPZsmXUqlULQ0NDwsPDuX37Nr6+vsDzF5EKhUL1mcDAQCwtLTlx4gQLFy7EyMioUv4WUPkiFoQK7OzZs7Rv3x59ff0SzxsYGBTbYryk5bCmpqYoFAoyMjIwNTUtk1g1JT8/n3nz5uHq6sr7779PSEgIZ86c4cyZMzx8+BBJkvDx8eHTTz9FqVRiYGAAwLVr14iPj8fMzIyvvvqKCRMmYG5uruHWvDqRdAWhFGVmZmJiYvKP17i6uqp9v2/fvmLXaGlpYWZmxq1bt6pc0j127Bj3799n9+7dPHr0iC1btnDlyhX69u3LnTt3CAsLw9PTE21tbWxsbDhw4AAAgwYNoqCgAENDQ5o3b14pEy6IpCsIpe6fhgPMzMxYuHCh2rEGDRq88n0qMy8vLw4fPkyPHj1o1qwZe/fuRV9fn/r16/P06VOqVauGtrY2hYWFvPPOO7z33nsAdO3alRUrVlBQUMDq1as13IrXJ5KuIJSDtLQ0tm3bhomJSYk94QULFtCrVy+cnZ01EF35e/z4MQcPHqRmzZoYGRnx7NkzTp8+TU5ODunp6UiSRE5ODtHR0bi4uBAfH8+9e/eoVq0aDRo0QJIknj59SvXq1TXdlFcmkq4glAMzMzMCAgIICwvDwsKCrKwsYmJimDZtGgqFArlcXikTyOt68uQJeXl5GBgY0K5dO5RKJfXr10ehUGBpacn169epU6cOJiYmfPPNNwDUrVuXmzdvcv/+fW7fvo2joyPjxo3TcEtenUi6glCK9PX1efbsWYnH9fX1CQwMZOXKlRgaGnLw4EESExORJAlfX99iVcOePn36whdylV2DBg0YM2YMJiYm7N69m40bNxIVFUWtWrWIioriyZMneHp60rVrV5o0aUJmZiYKhYKffvqJgoICfvjhB4YOHarpZrwWMU9XEEqRra0tFy5cKPFcaGgoBgYGzJw5U7W1zo4dO9i5c2eJCff69eu0a9euPMIuVxkZGTRu3BgjIyP09PSQy+Xs2rWLPXv2EBwczIMHD0hPT2ft2rU8fvyYNWvW8N5772FkZMT9+/dJTk7m9OnTyGQyTTfltYhlwIJQiiRJokGDBpw4cYLGjRurjt+6dQtfX1927tyJlpYWGzdu5OzZsyiVSgoKCsjJycHPz4+AgAAAoqOjWbJkCWfPntVQS97ci5YBR0REYGhoSMeOHdm+fTuNGjXi4cOH2NnZ0aZNG3Jzc4mIiODu3btMmjSJAQMGUK1aNeD57JBPP/2UmjVr0qRJE6ysrIrdv6IvAxZJVxBK2eDBg+nWrRsjRoxQO56dnU39+vVf6h6LFi2ievXqfPvtt2URYrn436SblpamKk1Zt25dGjVqREZGBhcvXqRt27YolUoWLVrE4sWLGTJkCO3bt6dfv360adMGeF4ac+zYsQwfPvyFz/T39+fYsWO4u7ujVCopKipCX18fSZKQyWRERkaWebv/jUi6glDKwsPDGTt2LMePH3+tl2P37t3Dzc2N+Ph4WrRoUfoBlpP/TbqSJJGVlcU333zDkiVLuH79Ordv32bDhg34+flhZGSEq6srubm5HDt2DA8PDzw8PGjTpg3W1tY4Ozvz+PFjvL29//G5xsbG5OXl0bdvX3x9fZk0aVJZN/WViDFdQShl7777Li4uLrz//vtER0e/9K+6SqWSo0ePMmTIEGbMmFGpE25JtLS0OHjwIH369EFbW5vNmzeTnp6OQqHg6dOnLF++nLCwMMLCwujZsycJCQlYW1szc+ZM0tLSSE1N5erVq1y7du1fn+Xk5ER6ejpWVla4ubmxatWqCjMGLHq6glAGlEolgYGBfPfdd8hkMmxtbbGxscHMzKxYEfMrV66QmJhIfHw8zZs3Z+7cuXh5eWkw+tLxvz3dwsJCXF1dqVGjBnfv3uW9994jOTmZjIwMWrZsSVZWFqGhoXz77be0atWK8+fP4+DgoHbPnJwcbt68iZ+fHy1btlQtEYbnwxdr164lODiYyMhIgoKCGDlyJObm5sybN4/Tp08TFBRUbBl2eRNJVxDKkFKpJC0tjdjYWKKjo8nIyCh2jbm5OY6Ojtjb22NqalplVqL9b9INCgpi8+bNZGdnY29vj7GxMZ6enmzatInZs2ezcOFCtm3bxrNnz1R/TkOGDFGN6WZmZjJ//nyMjIzYt28fDRs2ZM6cOar7p6amkpiYyLRp05AkiXHjxjFy5Ei6d+8OPH+B16RJE9X9NEUkXUEQyoSmtuvR0tIqtrIvOTmZ8+fPY2ZmVu7x/C8xpisIQpm4efMmkiSpvgIDA2nWrBlOTk40atSIa9eu4enpSb9+/dSu69evHzk5OUiSRLdu3YiIiCAiIgJ/f39Onjypum7Dhg04OTmhUChUx7Kzs3F1dSUyMlLty9HRscStkjRBJF1BEMrcvXv3mDt3Lr179yYoKAhfX1+MjY3R19fn3r17rF69mgcPHhAVFUXt2rWpW7cu8LzW8Lx585g3bx5hYWFq9xw/fjw6Ojps2LBBdUxbW5v4+HicnJzUvqKjo8u1vf9IEgRBKGPDhw+XPvnkE+n69evS06dPJaVSKY0ZM0basWOHpFAopJCQEGno0KFSeHi4FBcXp/pcr169JEmSpJSUFKlfv37S9evX1e6bnJwsNWjQQLp165YkSZKUlZUlvfvuu8We37t3b+nGjRtl1r5XIcZ0BUEoU0ePHmXy5MkkJSVhZGRU6vf/4osvSE5OZs+ePSiVSvLy8qhdu3apP6e0iKQrCEKZefr0Ke3atWP9+vX06dOnTJ5RUFCAjY0N33zzDYMGDSqTZ5QmkXQFQSgzn332GTdv3mTHjh1l+pzw8HBGjRpFcnIytWrVKtNnvSmRdAVBKBOJiYm4u7uTlJRUbDPOsjB27FiMjIwq/K4SIukKglDqFAoFXbt25YMPPmDChAnl8sycnBysra3Zv39/sZVsFYmYMiYIQqmZOHEicXFxbNiwAV1d3XLd2aFevXp89913jB8/HrlcTs+ePcnKyiq3578skXQFQSg1sbGx3L9/nwULFhAYGIi2dvmmmOHDh9O0aVNWrFjBo0ePuH79erk+/2WIpCsIQqm5c+cOa9euZezYsezYsYPvv/++3J598+ZNBgwYwNSpU/n222+pXbt2iUXUNU3skSYIQqlQKBTcv3+f+Ph4Ll26hIODQ7kmXVNTUwYNGsQHH3yApaUlFy9erJBJV/R0BUEoFX9vHqmjo0NgYCC7du3C2Ni43J6vpaXF+PHjSU5OxtzcnLt37xZbOlwRiNkLgiC80LNnz4iPjyc2NpaYmBgePHigdl5HRwdra2scHR2xsbFhw4YNLF26VK3Orabs3buXp0+f0rhxY2JiYoiLi+PJkydq1xgYGNCxY0ccHR1xcHBQ29eurIikKwhCMXl5eSxevJjAwEBMTU3p2LEjNjY2xZJSYWEhKSkpXLhwgbi4OCwsLJg/fz4eHh4aivy5W7du8eWXXxIcHEzbtm2xsbGhQ4cO1KlTR+26p0+fcvHiRS5cuEB8fDw9evTgyy+/pEOHDmUWmxjTFQRBzdOnT+nRowctWrTg0KFD/7ptUK9evQAoKiri0KFDjB49mm+//bbYxpzl5datW3Tp0oXBgwcTGRn5r5uB9uvXD3je7l9//RU3Nzd+//13HB0dyyQ+0dMVBEHN999/z9GjRwkKCnqtXSySkpIYOXIkN27ceK2NOd+Uv78/NWvWVNtV4lWEhISwdetWYmJiymQXD/EiTRAENatXryYgIOC1E0779u2xtbVl586dpRzZv8vOzmbv3r18+OGHr32PwYMHk5OTQ0xMTClG9n/E8IIgCCoZGRk8efIEGxubN7qPu7s7p06d4oMPPiilyF5OVFQUHTt2VBVB/5u/vz/5+fnA863gi4qK0NPTA0Amk7F//37Vtdra2vTo0YOTJ0/i5ORU6jGKpCsIgkp0dDSdOnV6YS/X1dW1WPGaK1euEB8fr3bMzs6OzZs3l1mcL3LmzBk6depU7HhQUBAA+fn5jBgxAk9PT8aMGfPC+9jb23PgwIEyiVEMLwiCoJKQkEC7du1eeN7AwAAXFxe1rxo1ahS7ztLSkvT0dJ4+fVqW4RaTlJSEtbV1iecSExPp378/mZmZtGnThqFDh7Jp0yZkMlmxa9u1a8fFixfLJEaRdAVBUJHL5RgaGv7jNa6urmpff/+a/t90dHTQ09OjqKiorEItkUKhQF9fX+1YWloaH3/8MTNnzmTZsmW4uroCsGbNGpKTk+nRo0ex8Vs9PT0UCkWZxCiGFwRBeGlmZmYsXLhQ7ViDBg00FM3LkSQJFxcXvv/+e7S1tdm1axcATZo04fvvvycmJoaGDRuWWzwi6QqC8K/S0tLYtm0bJiYmmJiYFDu/YMECevXqhbOzswai+2fm5ubUrVsXKysrLC0tAVi2bBkAqamp/PHHHzRv3rzc4hFJVxAENSVN3TczMyMgIICwsDAsLCzIysoiJiaGadOmoVAokMvlxebkamIJgI6ODnK5vNhxXV1d2rVrx549e9SO+/r6llh+Ui6Xl1lZSpF0BUFQMTU15ezZs8WO6+vro6+vT2BgICtXrsTQ0JCDBw+SmJiIJEn4+voycOBA1fX3799HT0+vxJdsZaldu3YkJycX2wRTW1ubpKQk+vfvr3b8ypUrJd4nOTn5H18ovgmRdAVBUOnSpQs//PBDiedCQ0MxMDBg5syZuLi44OXlxaxZs0q8Ni4uDgcHh3IvYt61a9cSy0kWFRXRvn37Enu6SqWy2PWxsbF07dq1TGIUy4AFQVCRy+XUrVuXs2fPqi0wuHXrFr6+vuzcuRMtLS02btzI2bNnUSqVFBQUkJOTg5+fHwEBAQAsXLiQxo0bs2DBgnKN/8GDB7Ru3Zro6Ghq166tOq5UKnny5MlL7RSsVCrp0aMHP/30U5mMUYukKwiCmlGjRmFiYsLUqVPVjmdnZ/9r8Rh4XjjGycmJiIgI1Yur8jR69Gjq16/PJ5988lqf379/Pxs3biQuLq5Mai+IpCsIgpq//voLV1dXNm3a9Mq76spkMmbPno2enh6//vprGUX4z9LT0+nSpQs+Pj6MHz++2JLgF3n27BnBwcF8++23HDhwoMxmYoikKwhCMUeOHMHPz4/27dvTr18/bG1tadOmDTo6OsWuffjwIRcuXODs2bPs2LGDbt26sXXrVoyMjDQQ+XM3b95k/vz57N+/nw4dOtChQwdsbGxKrKeblJREYmIicXFxdOnShYULF2JnZ1dmsYmkKwhCiQoKCti5cyfHjx8nLi6Ou3fvFhteKCwsJC8vDzs7OxwcHBg1ahTt27fXUMTFZWdnc/bsWdXOEXl5eWrnDQwMsLW1xdHREUdHR5o1a1bmMYmkKwjCS8nNzSU7O1vtmI6ODiYmJiX2gIWSiaQrCIJQjkTBG0EQhHIkkq4gCEI5EklXEAShHImkKwiCUI5E0hUEQShHIukKgiCUI5F0BUEQypFIuoIgCOXo/wEje+739SkB8AAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "features = list(df_tmp.columns[1:-2]) # x的表头\n",
    "#print(features)\n",
    "dataSet=np.array(df_tmp.values[:,1:]) # 数据处理为numpy.array类型，其实pandas.Dataframe类型更方便计算\n",
    "#print(dataSet)\n",
    "dt_Gini = createTree(dataSet, features)   #建立决策树，CART分类树\n",
    "print( 'CART分类树：\\n',dt_Gini)\n",
    "\n",
    "# 画出决策树\n",
    "tp.createPlot(dt_Gini)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "88f73989",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
